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

Nov 29, 2024 I’ll defend my PhD thesis on 29 November.
Oct 14, 2024 I visited Anuj Dawar and Benedikt Pago at the University of Cambridge.
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!

selected publications

  1. metathm.png
    An Algorithmic Meta Theorem for Homomorphism Indistinguishability
    Tim Seppelt
    In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), Aug 2024
  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
  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