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…