Publications
Preprints and working papers
44. A Proof of the Weak Roberson Conjecture
Arnar Ágúst Kristjánsson, Benjamin Moore, Daniel Neuen, David E. Roberson, Tim Seppelt, Benjamin Young.
Working paper (2026).
Working paper
43. Topological and Geometric Perspectives on Homomorphism Indistinguishability
Josse van Dobben de Bruyn, Jérémie Marquès, David E. Roberson, Tim Seppelt, Gian Luca Spitzer, Peter Zeman.
Preprint (2026).
arXiv:2610.07927
42. Free Inhomogeneous Wreath Product of Compact Quantum Groups
Josse van Dobben de Bruyn, Amaury Freslon, Prem Nigam Kar, David E. Roberson, Peter Zeman.
Preprint (2025).
arXiv:2504.13826
41. Group Invariant Quantum Latin Squares
Arnbjörg Soffía Árnadóttir, David E. Roberson.
Preprint (2025).
arXiv:2501.00196
40. Quantum symmetry vs nonlocal symmetry
David E. Roberson, Simon Schmidt.
Preprint (2020).
arXiv:2012.13328
Publications
39. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree
David E. Roberson.
Journal of Combinatorial Theory, Series B 181, 1–61 (2026).
Published version · arXiv:2206.10321
38. Asymmetric graphs with quantum symmetry
Josse van Dobben de Bruyn, David E. Roberson, Simon Schmidt.
Proceedings of the London Mathematical Society 131, e70098 (2025).
Published version · arXiv:2311.04889
37. Quantum Perfect Matchings
David Cui, Laura Mančinska, Seyed Sajjad Nezhadi, David E. Roberson.
Annales Henri Poincaré (2025).
Published version · arXiv:2502.05136
Selected for presentation at TQC 2025.
36. NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability (Full version)
Prem Nigam Kar, David E. Roberson, Tim Seppelt, Peter Zeman.
Quantum 10, 1989 (2026).
Published version · arXiv:2407.10635
35. NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability (Extended abstract)
Prem Nigam Kar, David E. Roberson, Tim Seppelt, Peter Zeman.
52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), LIPIcs 334, 105:1–105:19 (2025).
Published version
34. Quantum Automorphism Groups of Lexicographic Products of Graphs
Arnbjörg Soffía Árnadóttir, Josse van Dobben de Bruyn, Prem Nigam Kar, David E. Roberson, Peter Zeman.
Journal of the London Mathematical Society 111(4) (2025).
Published version · arXiv:2402.12344
33. Quantum automorphism groups of trees
Josse van Dobben de Bruyn, Prem Nigam Kar, David E. Roberson, Simon Schmidt, Peter Zeman.
Journal of Noncommutative Geometry 20(2), 489–505 (2026).
Published version · arXiv:2311.04891
32. Transitive Nonlocal Games
Prem Nigam Kar, Jitendra Prakash, David E. Roberson.
Journal of Mathematical Physics 65(7), 072202 (2024).
Published version · arXiv:2312.12040
31. Graph isomorphism: Physical resources, optimization models, and algebraic characterizations
Laura Mančinska, David E. Roberson, Antonios Varvitsiotis.
Mathematical Programming 205, 617–660 (2024).
Published version · arXiv:2004.10893
30. Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability (Full version)
David E. Roberson, Tim Seppelt.
TheoretiCS 3, Article 20 (2024).
Published version · arXiv:2302.10538
29. Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability (Extended abstract)
David E. Roberson, Tim Seppelt.
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), LIPIcs 261, 101:1–101:18 (2023).
Published version
28. Solution group representations as quantum symmetries of graphs
David E. Roberson, Simon Schmidt.
Journal of the London Mathematical Society 106(4) (2022).
Published version · arXiv:2111.12362
27. Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph
Illya V. Hicks, Boris Brimkov, Louis Deaett, Ruth Haas, Derek Mikesell, David E. Roberson, Logan Smith.
INFORMS Journal on Computing 34(6) (2022).
Published version
26. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs
Laura Mančinska, David E. Roberson.
61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), 661–672 (2020).
Published version · arXiv:1910.06958
Selected as a short plenary talk at QIP 2021.
25. Limit of Gaussian operations and measurements for Gaussian state discrimination, and its application to state comparison
David E. Roberson, Shuro Izumi, Wojciech Roga, Jonas S. Neergaard-Nielsen, Masahiro Takeoka, Ulrik L. Andersen.
Physical Review A 103, 022423 (2021).
Published version · arXiv:2009.00108
24. Nonlocal Games and Quantum Permutation Groups
Martino Lupini, Laura Mančinska, David E. Roberson.
Journal of Functional Analysis 279(5), 108592 (2020).
Published version · arXiv:1712.01820
23. Perfect Strategies for Non-Local Games
Martino Lupini, Laura Mančinska, Vern I. Paulsen, David E. Roberson, Giannicola Scarpa, Simone Severini, Ivan G. Todorov, Andreas Winter.
Mathematical Physics, Analysis and Geometry 23, Article 7 (2020).
Published version · arXiv:1804.06151
22. Cores of Cubelike Graphs
Laura Mančinska, Irene Pivotto, David E. Roberson, Gordon Royle.
European Journal of Combinatorics 87, 103092 (2020).
Published version · arXiv:1808.02051
21. Vector Coloring the Categorical Product of Graphs
Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, Antonios Varvitsiotis.
Mathematical Programming 182, 275–314 (2020).
Published version · arXiv:1801.08243
20. Quantum and Non-Signalling Graph Isomorphisms
Albert Atserias, Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, Antonios Varvitsiotis.
Journal of Combinatorial Theory, Series B 136, 289–328 (2019).
Published version · arXiv:1611.09837
19. Algebras, Graphs and Thetas
Marcel K. de Carli Silva, Gabriel Coutinho, Chris Godsil, David E. Roberson.
Electronic Notes in Theoretical Computer Science 346, 275–283 (2019).
Published version · arXiv:1910.06260
18. Graph Homomorphisms via Vector Colorings
Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, Antonios Varvitsiotis.
European Journal of Combinatorics 79, 244–261 (2019).
Published version · arXiv:1610.10002
17. Relaxations of Graph Isomorphism
Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, Antonios Varvitsiotis.
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), LIPIcs 80, 76:1–76:14 (2017).
Published version
16. Universal completability, least eigenvalue frameworks, and vector colorings
Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, Antonios Varvitsiotis.
Discrete & Computational Geometry 58(2), 265–292 (2017).
Published version · arXiv:1512.04972
15. Note on von Neumann and Rényi entropies of a graph
Michael Dairyko, Leslie Hogben, Jephian C.-H. Lin, Joshua Lockhart, David E. Roberson, Simone Severini, Michael Young.
Linear Algebra and its Applications 521, 240–253 (2017).
Published version · arXiv:1609.00420
14. Orthogonal Representations, Projective Rank, and Fractional Minimum Positive Semidefinite Rank: Connections and New Directions
Leslie Hogben, Kevin F. Palmowski, David E. Roberson, Simone Severini.
Electronic Journal of Linear Algebra 32, 98–115 (2017).
Published version · arXiv:1502.00016
13. Sabidussi versus Hedetniemi for Three Variations of Chromatic Number
Chris Godsil, David E. Roberson, Robert Šámal, Simone Severini.
Combinatorica 36(4), 395–415 (2016).
Published version · arXiv:1305.5545
12. Oddities of Quantum Colorings
Laura Mančinska, David E. Roberson.
Baltic Journal of Modern Computing 4(4), 846–859 (2016).
Published version · arXiv:1801.03542
11. A new property of the Lovász number and duality relations between graph parameters
Antonio Acín, Runyao Duan, David E. Roberson, Ana Belén Sainz, Andreas Winter.
Discrete Applied Mathematics 216, Part 3, 489–501 (2017).
Published version · arXiv:1505.01265
10. Fractional Zero Forcing via Three-color Forcing Games
Leslie Hogben, Kevin F. Palmowski, David E. Roberson, Michael Young.
Discrete Applied Mathematics 213, 114–129 (2016).
Published version · arXiv:1509.02883
9. Quantum Homomorphisms
Laura Mančinska, David E. Roberson.
Journal of Combinatorial Theory, Series B 118, 228–267 (2016).
Published version · arXiv:1212.1724
8. Homomorphisms of Strongly Regular Graphs
David E. Roberson.
Algebraic Combinatorics 2(4), 481–497 (2019).
Published version · arXiv:1601.00969
7. Conic Formulations of Graph Homomorphisms
David E. Roberson.
Journal of Algebraic Combinatorics 43(4), 877–913 (2016).
Published version · arXiv:1411.6723
6. On Deciding the Existence of Perfect Entangled Strategies for Nonlocal Games
Laura Mančinska, David E. Roberson, Antonios Varvitsiotis.
Chicago Journal of Theoretical Computer Science, Article 5 (2016).
Published version · arXiv:1506.07429
5. Graph Cores via Universal Completability
Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, Antonios Varvitsiotis.
Electronic Notes in Discrete Mathematics 49, 337–344 (EuroComb 2015) (2015).
Published version
4. Bounds on Entanglement Assisted Source-Channel Coding via the Lovász Theta Number and its Variants
Toby Cubitt, Laura Mančinska, David E. Roberson, Simone Severini, Dan Stahlke, Andreas Winter.
IEEE Transactions on Information Theory 60(11), 7330–7344 (2014).
Published version · arXiv:1310.7120
3. Two Characterizations of Nonlocal Games with Perfect Maximally Entangled Strategies
Laura Mančinska, David E. Roberson, Antonios Varvitsiotis.
14th Asian Quantum Information Science Conference (AQIS 2014) (2014).
Conference record
2. Cores of Vertex Transitive Graphs
David E. Roberson.
The Electronic Journal of Combinatorics 20(2), P45 (2013).
Published version · arXiv:1302.4470
1. Häggkvist-Hell Graphs: A Class of Kneser-colorable Graphs
David E. Roberson.
Discrete Mathematics 312(5), 837–853 (2012).
Published version · arXiv:1008.2199