Showing cs.CCShow all
2 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.CC2024
Lower Bounds for Symmetric Circuits for the Determinant
Anuj Dawar, Gregory Wilsenach
Dawar and Wilsenach (ICALP 2020) introduce the model of symmetric arithmetic circuits and show an exponential separation between the sizes of symmetric circuits for computing the d…