Counting (with) homomorphisms

Søgeresultater

• 2026

  Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing

  Černý, M. & Seppelt, T., 2026, Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Bind 364. s. 1-20

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Graph Classes 100%
  • Homomorphism Indistinguishability 100%
  • Polynomial Identity Testing 100%
  • Polynomial 100%
  • Homomorphism 100%

• NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

  Kar, P. N., Roberson, D. E., Seppelt, T. & Zeman, P., 28 jan. 2026, I: Quantum. 10, 1989, 1989.

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  • Homomorphism Indistinguishability 100%
  • Quantum Isomorphism 100%
  • Homomorphism 100%
  • Indistinguishability 100%
  • Planar Graph 75%

• Symmetric Algebraic Circuits and Homomorphism Polynomials

  Dawar, A., Pago, B. & Seppelt, T., jan. 2026, LIPIcs, Volume 362, ITCS 2026. Shubhangi, S. (red.). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Bind 362. s. 46:1-46:15 15 s.

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Circuit Polynomial 100%
  • Polynomial 100%
  • Homomorphism 100%
  • Symmetric Circuits 66%
  • Counting Polynomial 66%

• 2025

  Can You Link Up With Treewidth?

  Curticapean, R.-C., Döring, S., Neuen, D. & Wang, J., 24 feb. 2025, Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science. Beyersdorff, O., Pilipczuk, M., Pimentel, E. & Kim Thắn, N. (red.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Bind 327. 24 s. 28. (Leibniz International Proceedings in Informatics (LIPIcs), Bind 327).

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Tight Lower Bound 100%
  • Exponential Time Hypothesis 100%
  • Treewidth 100%
  • Exponential Time 100%
  • Maximum Degree 66%

• Counting Small Induced Subgraphs: Hardness via Fourier Analysis

  Curticapean, R.-C. & Neuen, D., 2025, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, s. 3677 - 3695 19 s.

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Optimal Exponent 100%
  • Fourier Analysis 100%
  • Edge 100%
  • Induced Subgraph 100%
  • Schmitt 50%

• Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial

  Curticapean, R.-C., Döring, S. & Neuen, D., 1 okt. 2025, Proceedings of the 33rd Annual European Symposium on Algorithms. s. 96:2 - 96:16 16 s. 96

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Scorpion 100%
  • Monotone Property 100%
  • Hereditary Property 100%
  • Graph Properties 50%
  • Restricted Type 25%

• Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

  Curticapean, R.-C., Björklund, A., Husfeldt, T., Kaski, P. & Pratt, K., 1 jan. 2025, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. s. 2804-2818 15 s.

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Chromatic number 100%
  • Rank Conjecture 100%
  • Asymptotic Rank 100%
  • Asymptotics 100%
  • Chromatic Number 100%

• Homomorphism Tensors and Linear Equations

  Grohe, M., Rattan, G. & Seppelt, T., 2 apr. 2025, I: Advances in Combinatorics.

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  • Linear Equations 100%
  • Tensor Equation 100%
  • Linear Equation 100%
  • Homomorphism Indistinguishability 60%
  • Treedepth 40%

• Monotone Bounded-Depth Complexity of Homomorphism Polynomials

  C. S., B., Curticapean, R.-C., Chen, S. & Dwivedi, P., 20 aug. 2025, Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Bind 345. s. 19:1--19:18 18 s. 19

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Depth Complexity 100%
  • Bounded Depth 100%
  • Homomorphism Polynomials 100%
  • Polynomial 100%
  • Homomorphism 100%

• NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

  Kar, P. N., Roberson, D. E., Seppelt, T. & Zeman, P., 2025, International Colloquium on Automata, Languages, and Programming (ICALP). Bind 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). s. 1-19 19 s.

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Quantum Isomorphism 100%
  • SDP Relaxation 40%
  • Semidefinite Relaxation 40%
  • Quantum Groups 20%
  • Lasserre Hierarchy 20%

• The Complexity of Homomorphism Reconstructibility

  Böker, J., Härtel, L., Runde, N., Seppelt, T. & Standke, C., 18 aug. 2025, I: ACM Transactions on Computation Theory. s. 1-37 37 s.

  Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

  Åben adgang

  • Reconstructibility 100%
  • Finite Inputs 28%
  • Natural Number 25%
  • Finite Input 25%
  • #P-hard Problem 14%

• Which Graph Motif Parameters Count?

  Bläser, M., Curticapean, R.-C., Dörfler, J. & Ikenmeyer, C., 20 aug. 2025, Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science. 18 s.

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  • Combinatorial Interpretations 100%
  • Negative Coefficient 66%
  • Integer Coefficient 66%
  • Relational Structure 33%
  • Ramsey's Theorem 33%

• 2024

  Count on CFI graphs for #P-hardness

  Curticapean, R.-C., 2024, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024. Society for Industrial and Applied Mathematics, s. 1854 - 1871

  Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

  Åben adgang

  Fil

  • Homomorphism 100%
  • Linear Combination 100%
  • CI-graph 100%
  • #P-hardness 100%
  • Polynomial Time 60%