Search Results

Documents authored by Roberson, David

Found 2 Possible Name Variants:

Roberson, David E.

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.105
NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

Authors: Prem Nigam Kar, David E. Roberson, Tim Seppelt, and Peter Zeman

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Mančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they are homomorphism indistinguishable over the class of planar graphs. Atserias et al. [JCTB'19] proved that quantum isomorphism is undecidable in general. The NPA hierarchy gives a sequence of semidefinite programming relaxations of quantum isomorphism. Recently, Roberson and Seppelt [ICALP'23] obtained a homomorphism indistinguishability characterization of the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism. We prove a quantum analogue of this result by showing that each level of the NPA hierarchy of SDP relaxations for quantum isomorphism of graphs is equivalent to homomorphism indistinguishability over an appropriate class of planar graphs. By combining the convergence of the NPA hierarchy with the fact that the union of these graph classes is the set of all planar graphs, we are able to give a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the use of the theory of quantum groups. This homomorphism indistinguishability characterization also allows us to give a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.
Cite as

Prem Nigam Kar, David E. Roberson, Tim Seppelt, and Peter Zeman. NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 105:1-105:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kar_et_al:LIPIcs.ICALP.2025.105,
  author =	{Kar, Prem Nigam and Roberson, David E. and Seppelt, Tim and Zeman, Peter},
  title =	{{NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{105:1--105:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.105},
  URN =		{urn:nbn:de:0030-drops-234828},
  doi =		{10.4230/LIPIcs.ICALP.2025.105},
  annote =	{Keywords: Quantum isomorphism, NPA hierarchy, homomorphism indistinguishability}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.101
Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability

Authors: David E. Roberson and Tim Seppelt

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We show that feasibility of the t^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 ℒ_t of graphs such that graphs G and H are not distinguished by the t^th level of the Lasserre hierarchy if and only if they admit the same number of homomorphisms from any graph in ℒ_t. By analysing the treewidth of graphs in ℒ_t we prove that the 3t^th level of Sherali-Adams linear programming hierarchy is as strong as the t^th level of Lasserre. Moreover, we show that this is best possible in the sense that 3t cannot be lowered to 3t-1 for any t. The same result holds for the Lasserre hierarchy with non-negativity constraints, which we similarly characterise in terms of homomorphism indistinguishability over a family ℒ_t^+ of graphs. Additionally, we give characterisations of level-t Lasserre with non-negativity constraints in terms of logical equivalence and via a graph colouring algorithm akin to the Weisfeiler-Leman algorithm. This provides a polynomial time algorithm for determining if two given graphs are distinguished by the t^th level of the Lasserre hierarchy with non-negativity constraints.
Cite as

David E. Roberson and Tim Seppelt. Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 101:1-101:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{roberson_et_al:LIPIcs.ICALP.2023.101,
  author =	{Roberson, David E. and Seppelt, Tim},
  title =	{{Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{101:1--101:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.101},
  URN =		{urn:nbn:de:0030-drops-181531},
  doi =		{10.4230/LIPIcs.ICALP.2023.101},
  annote =	{Keywords: Lasserre hierarchy, homomorphism indistinguishability, Sherali-Adams hierarchy, treewidth, semidefinite programming, linear programming, graph isomorphism}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.76
Relaxations of Graph Isomorphism

Authors: Laura Mancinska, David E. Roberson, Robert Samal, Simone Severini, and Antonios Varvitsiotis

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We introduce a nonlocal game that captures and extends the notion of graph isomorphism. This game can be won in the classical case if and only if the two input graphs are isomorphic. Thus, by considering quantum strategies we are able to define the notion of quantum isomorphism. We also consider the case of more general non-signalling strategies, and show that such a strategy exists if and only if the graphs are fractionally isomorphic. We prove several necessary conditions for quantum isomorphism, including cospectrality, and provide a construction for producing pairs of non-isomorphic graphs that are quantum isomorphic. We then show that both classical and quantum isomorphism can be reformulated as feasibility programs over the completely positive and completely positive semidefinite cones respectively. This leads us to considering relaxations of (quantum) isomorphism arrived at by relaxing the cone to either the doubly nonnegative (DNN) or positive semidefinite (PSD) cones. We show that DNN-isomorphism is equivalent to the previous defined notion of graph equivalence, a polynomial-time decidable relation that is related to coherent algebras. We also show that PSD-isomorphism implies several types of cospectrality, and that it is equivalent to cospectrality for connected 1-walk-regular graphs. Finally, we show that all of the above mentioned relations form a strict hierarchy of weaker and weaker relations, with non-singalling/fractional isomorphism being the weakest. The techniques used are an interesting mix of algebra, combinatorics, and quantum information.
Cite as

Laura Mancinska, David E. Roberson, Robert Samal, Simone Severini, and Antonios Varvitsiotis. Relaxations of Graph Isomorphism. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 76:1-76:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mancinska_et_al:LIPIcs.ICALP.2017.76,
  author =	{Mancinska, Laura and Roberson, David E. and Samal, Robert and Severini, Simone and Varvitsiotis, Antonios},
  title =	{{Relaxations of Graph Isomorphism}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{76:1--76:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.76},
  URN =		{urn:nbn:de:0030-drops-74697},
  doi =		{10.4230/LIPIcs.ICALP.2017.76},
  annote =	{Keywords: graph isomorphism, quantum information, semidefinite programming}
}

Roberson, David

Document
DOI: 10.4230/LIPIcs.TQC.2014.48
Bounds on Entanglement Assisted Source-channel Coding Via the Lovász Theta Number and Its Variants

Authors: Toby Cubitt, Laura Mancinska, David Roberson, Simone Severini, Dan Stahlke, and Andreas Winter

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

Abstract
We study zero-error entanglement assisted source-channel coding (communication in the presence of side information). Adapting a technique of Beigi, we show that such coding requires existence of a set of vectors satisfying orthogonality conditions related to suitably defined graphs G and H. Such vectors exist if and only if theta(G) <= theta(H) where theta represents the Lovász number. We also obtain similar inequalities for the related Schrijver theta^- and Szegedy theta^+ numbers. These inequalities reproduce several known bounds and also lead to new results. We provide a lower bound on the entanglement assisted cost rate. We show that the entanglement assisted independence number is bounded by the Schrijver number: alpha^*(G) <= theta^-(G). Therefore, we are able to disprove the conjecture that the one-shot entanglement-assisted zero-error capacity is equal to the integer part of the Lovász number. Beigi introduced a quantity beta as an upper bound on alpha^* and posed the question of whether beta(G) = \lfloor theta(G) \rfloor. We answer this in the affirmative and show that a related quantity is equal to \lceil theta(G) \rceil. We show that a quantity chi_{vect}(G) recently introduced in the context of Tsirelson's conjecture is equal to \lceil theta^+(G) \rceil.
Cite as

Toby Cubitt, Laura Mancinska, David Roberson, Simone Severini, Dan Stahlke, and Andreas Winter. Bounds on Entanglement Assisted Source-channel Coding Via the Lovász Theta Number and Its Variants. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 48-51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{cubitt_et_al:LIPIcs.TQC.2014.48,
  author =	{Cubitt, Toby and Mancinska, Laura and Roberson, David and Severini, Simone and Stahlke, Dan and Winter, Andreas},
  title =	{{Bounds on Entanglement Assisted Source-channel Coding Via the Lov\'{a}sz Theta Number and Its Variants}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{48--51},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.48},
  URN =		{urn:nbn:de:0030-drops-48054},
  doi =		{10.4230/LIPIcs.TQC.2014.48},
  annote =	{Keywords: source-channel coding, zero-error capacity, Lov\'{a}sz theta}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.212
Graph Homomorphisms for Quantum Players

Authors: Laura Mancinska and David Roberson

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

Abstract
A homomorphism from a graph X to a graph Y is an adjacency preserving mapping f:V(X) -> V(Y). We consider a nonlocal game in which Alice and Bob are trying to convince a verifier with certainty that a graph X admits a homomorphism to Y. This is a generalization of the well-studied graph coloring game. Via systematic study of quantum homomorphisms we prove new results for graph coloring. Most importantly, we show that the Lovász theta number of the complement lower bounds the quantum chromatic number, which itself is not known to be computable. We also show that other quantum graph parameters, such as quantum independence number, can differ from their classical counterparts. Finally, we show that quantum homomorphisms closely relate to zero-error channel capacity. In particular, we use quantum homomorphisms to construct graphs for which entanglement-assistance increases their one-shot zero-error capacity.
Cite as

Laura Mancinska and David Roberson. Graph Homomorphisms for Quantum Players. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 212-216, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{mancinska_et_al:LIPIcs.TQC.2014.212,
  author =	{Mancinska, Laura and Roberson, David},
  title =	{{Graph Homomorphisms for Quantum Players}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{212--216},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.212},
  URN =		{urn:nbn:de:0030-drops-48179},
  doi =		{10.4230/LIPIcs.TQC.2014.212},
  annote =	{Keywords: graph homomorphism, nonlocal game, Lov\'{a}sz theta, quantum chromatic number, entanglement}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact