David E. Roberson
Associate Professor
Section for Algorithms, Logic, and Graph Theory (AlgoLoG)
Department of Applied Mathematics and Computer Science
Technical University of Denmark (DTU)
and
Centre for the Mathematics of Quantum Theory (QMATH)
University of Copenhagen
Curriculum Vitae
Google Scholar
I have recently been awarded a Carlsberg Young Researcher fellowship for my project "Quantum Graph Theory".
Preprints
32. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree. Submitted to the Journal of Combinatorial Theory, Series B. arXiv:2206.10321
31. Quantum symmetry vs nonlocal symmetry. With Simon Schmidt. Under revision at Quantum. arXiv:2012.13328
Publications
30. Graph isomorphism: Physical resources, optimization models, and algebraic characterizations. With Laura Mančinska and Antonios Varvitsiotis. Mathematical Programming, 2023. arXiv:2004.10893
29. Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability. With Tim Seppelt. Leibniz International Proceedings in Informatics (LIPIcs), 261, 2023. Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). arXiv:2302.10538
28. Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph. With Illya V. Hicks, Boris Brimkov, Louis Deaett, Ruth Haas, Derek Mikesell, and Logan Smith. INFORMS Journal on Computing, 34(6), 2022.
27. Solution group representations as quantum symmetries of graphs. With Simon Schmidt. Journal of the London Mathematical Society, 106(4):3379–3410, 2022. arXiv:2111.12362
26. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. With Laura Mančinska. Proceedings of the 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), 661–672. Presented as a short plenary talk at the 24th Conference on Quantum Information Processing (QIP '21), 2021. arXiv:1910.06958
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. Neergard-Nielsen, Masahiro Takeoka, Ulrik L. Andersen. Physical Review A, 103, 022423, 2021. arXiv:2009.00108yoo
24. Cores of Cubelike Graphs. With Laura Mančinska, Irene Pivotto, and Gordon Royle. European Journal of Combinatorics, 87, 2020. arXiv:1808.02051
23. Nonlocal Games and Quantum Permutation Groups. With Martino Lupini, and Laura Mančinska. Journal of Functional Analysis, 279(5), 2020. arXiv:1712.01820
22. Perfect Strategies for Non-signalling Games. With Martino Lupini, Laura Mančinska, Vern Paulsen, Giannicola Scarpa, Simone Severini, Ivan Todorov, and Andreas Winter. Mathematical Physics, Analysis and Geometry, 23, 2020. arXiv:1804.06151
21. Vector Coloring the Categorical Product of Graphs. With Chris Godsil, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. Mathematical Programming, 182:275–314, 2020. arXiv:1801.08243
20. Algebras, Graphs, and Thetas. With Marcel K. de Carli Silva, Gabriel Coutinho, and Chris Godsil. Electronic Notes in Theoretical Computer Science, 346:275–283, 2019. arXiv:1910.06260
19. Graph Homomorphisms via Vector Colorings. With Chris Godsil, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. European Journal of Combinatorics, 79:244–261, 2019. arXiv:1610.10002
18. Homomorphisms of Strongly Regular Graphs. Algebraic Combinatorics, 2(4):481–497, 2019. arXiv:1601.00969
17. Quantum and Non-Signalling Graph Isomorphisms. With Laura Mančinska, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. Journal of Combinatorial Theory, Series B, 136:289–328, 2019. arXiv:1611.09837
16. Relaxations of Graph Isomorphism. With Laura Mančinska, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. Leibniz International Proceedings in Informatics (LIPIcs), 80, 2017. Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017).
15. Universal completability, least eigenvalue frameworks, and vector colorings. With Chris Godsil, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. Discrete & Computational Geometry, 58(2):265–292, 2017. arXiv:1512.04972
14. Note on von Neumann and Rényi entropies of a graph. With Michael Dairyko, Leslie Hogben, Jephian C.-H. Lin, Joshua Lockhart, Simone Severini, and Michael Young. Linear Algebra and its Applications, 521:240–253, 2017. arXiv:1609.00420
13. Orthogonal Representations, Projective Rank, and Fractional Minimum Positive Semidefinite Rank: Connections and New Directions. With Leslie Hogben, Kevin F. Palmowski, and Simone Severini. Electronic Journal of Linear Algebra, 32:98–115, 2017. arXiv:1502.00016
12. Sabidussi versus Hedetniemi for Three Variations of Chromatic Number. With Chris Godsil, Robert Šámal, and Simone Severini. Combinatorica, 36(4):395–415, 2016. arXiv:1305.5545
11. Oddities of Quantum Colorings. With Laura Mančinska. Baltic Journal of Modern Computing, 4(4):846–859, 2016. arXiv:1801.03542
10. Conic Formulations of Graph Homomorphisms. Journal of Algebraic Combinatorics, 43(4):877–913, 2016. arXiv:1411.6723
9. Fractional Zero Forcing via Three-color Forcing Games. With Leslie Hogben, Kevin F. Palmowski, and Michael Young. Discrete Applied Mathematics, 213(20):114–129, 2016. arXiv:1509.02883
8. On deciding the existence of perfect entangled strategies for nonlocal games. With Laura Mančinska, and Antonios Varvitsiotis. Chicago Journal of Theoretical Computer Science, 2016. arXiv:1506.07429
7. Quantum Homomorphisms. With Laura Mančinska. Journal of Combinatorial Theory, Series B, 118:228–267, 2016. Presented as a highlighted talk at the 9th Conference on the Theory of Quantum Computation and Cryptography, 2014. arXiv:1212.1724
6. A new property of the Lovász theta function and duality relations between graph parameters. With Antonio Acín, Runyao Duan, Ana Belén Sainz, Andreas Winter. Discrete Applied Mathematics, 216(3):489–501, 2016. arXiv:1505.01265
5. Graph Cores via Universal Completability. With Chris Godsil, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. Electronic Notes in Combinatorics, 49:337–344, 2015. Proceedings of Eurocomb '15.
4. Bounds on Entanglement Assisted Source-Channel Coding via the Lovasz Theta Number and its Variants. With Toby Cubitt, Laura Mančinska, Simone Severini, Dan Stahlke, and Andreas Winter. IEEE Transactions on Information Theory, 60(11):7330–7344, 2014. arXiv:1310.7120
3. Two Characterizations of Nonlocal Games with Perfect Maximally Entangled Strategies. With Laura Mančinska, and Antonios Varvitsiotis. Proceedings of the 14th Asian Quantum Information Science Conference (AQIS'14).
2. Cores of Vertex Transitive Graphs. The Electronic Journal of Combinatorics, 20(2):P45, 2013. arXiv:1302.4470
1. Häggkvist-Hell Graphs: A Class of Kneser-colorable Graphs. Discrete Mathematics, 312(5):837–853, 2012. arXiv:1008.2199