Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
Symmetric Algebraic Circuits and Homomorphism Polynomials
Anuj Dawar, Benedikt Pago, Tim Seppelt
The central open question of algebraic complexity is whether VP is unequal to VNP, which is saying that the permanent cannot be represented by families of polynomial-size algebraic…
cs.CC2026
Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
Prateek Dwivedi, Benedikt Pago, Tim Seppelt
Valiant's conjecture asserts that the circuit complexity classes VP and VNP are distinct, meaning that the permanent does not admit polynomial-size algebraic circuits. As it is the…
cs.CC2025
Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
Marek Äerný, Tim Seppelt
Two graphs and are homomorphism indistinguishable over a graph class if they admit the same number of homomorphisms from every graph . Many…