Tim Seppelt

PhD student at RWTH Aachen University

Foto Website square.JPG

I’m a fourth-year PhD student at RWTH Aachen University. My supervisors are Prof Martin Grohe and Prof Michael Schaub. I’m funded by the German Research Foundation (DFG) via Research Training Group 2236 (UnRAVeL).

I’m interested in graphs and more specifically in theoretical and algorithmic notions concerning the similarity of two graphs. A central theme of my PhD is homomorphism indistinguishability, which describes the similarity of graphs in terms of numbers of homomorphisms.

news

Jul 16, 2024 Our new preprint NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability (with Prem Nigam Kar, David E. Roberson, and Peter Zeman) is now available on arXiv. In this paper, we give a more elementary proof of the breakthrough result by Mančinska and Roberson [FOCS 2020] equating homomorphism indistinguishability over planar graphs and quantum isomorphism by characterising the feasibility of each level of the NPA semidefinite programming hierarchy for quantum isomorphism as a homomorphism indistinguishability relation over a suitable class of planar graphs of bounded treewidth. Check it out!
Jul 8, 2024 An extended version of our paper Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability (with David E. Roberson) was accepted for the Diamond Open Access journal TheoretiCS.
Jun 25, 2024 My paper An Algorithmic Meta Theorem for Homomorphism Indistinguishability was accepted for MFCS 2024. See you in Bratislava!
Feb 15, 2024 My new preprint An Algorithmic Meta Theorem for Homomorphism Indistinguishability is now available on arXiv. The slides of the talk I gave about it at AlMoTh 2024 are also online. Check them out!
Dec 13, 2023 Our paper The Complexity of Homomorphism Reconstructibility (with Jan Böker, Louis Härtel, Nina Runde, and Christoph Standke) was accepted for STACS 2024.

selected publications

  1. mfcs23.png
    Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
    Tim Seppelt
    In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Aug 2023
  2. icalp23.png
    Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
    David E. Roberson, and Tim Seppelt
    In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), Jul 2023
    accepted for TheoretiCS
  3. soda23.png
    Weisfeiler-Leman and Graph Spectra
    Gaurav Rattan, and Tim Seppelt
    In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Feb 2023
  4. background.jpg
    Homomorphism Tensors and Linear Equations
    Martin GroheGaurav Rattan, and Tim Seppelt
    In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Jul 2022