Extending Symmetric Circuits
summary
Extends Anderson and Daw’s circuit model and proves a support theorem showing every gate in a P-uniform symmetric circuit with matrix-symmetric gates has constant-size support, letting the construction translate such circuit families into fixed-point logic with rank. Weakening symmetry (structure-aware or partial orbits) fails to capture CPT, and adding arbitrary symmetric Boolean functions gives no extra power beyond majority; the concrete result is that P-uniform symmetric circuits with rank operators capture FPR.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 2:08Fixed point with counting
- 3:51Choices polynomial time
- 5:32Radtke logic
- 6:43Circuit model
- 10:34Extending the notion
- 11:25Weakening symmetry
- 13:03Encoding
- 14:02Invariance group
- 16:52Matrix symmetric functions
- 17:33Matrix symmetric gates
- 18:26Summary
related talks
01h 03mThe Classification Program for Counting Problems II
57mTowards P≠NP from Extended Frege Lower Bounds
47mNatural Proofs in Algebraic Circuit Complexity
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
54mConstraints, Gadgets, and Invariants
50mRandom Combinatorial Matrices
56mApproximate Counting II
01h 02mConsistency of NEXP Not in P/poly in a Strong Theory