Biblio Discovery — Demo Discovery Service

3 results for "Tim Seppelt"

Showing 1–3 · 0.23 seconds · RSS

  1. Journal Article

    Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability

    David E. Roberson; Tim Seppelt

    TheoretiCS, Vol. Volume 3 · 2024 · English · DOAJ Scopus

    We show that feasibility of the $t^\text{th}$ level of the Lasserre semidefinite programming hierarchy for graph isomorphism can be expressed as a homomorphism indistinguishability relation. In other words, we define a class $\mathcal{L}_t$ of graphs such that graphs $G$ and $H$ are not…

  2. Journal Article

    Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth

    Isolde Adler; Eva Fluck; Tim Seppelt et al.

    Logical Methods in Computer Science, Vol. Volume 22 No. ue 2 · 2026 · English · DOAJ Scopus

    We study the expressive power of first-order logic with counting quantifiers, especially the $k$-variable and quantifier-rank-$q$ fragment, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio~(2021) proved that two graphs satisfy the same $k$-variable and quantifier-rank-$q$…

  3. Journal Article

    NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

    Prem Nigam Kar; David E. Roberson; Tim Seppelt et al.

    Quantum, Vol. 10 · 2026 · English · DOAJ Scopus

    …the study of its relaxations. In the classical setting, Roberson and Seppelt [ICALP'23] characterized the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism in terms of equality of homomorphism counts from an appropriate graph class. The…