Smaller ACC0 Circuits for Symmetric Functions

on YouTube ↗23m

" summary

Every symmetric Boolean function on n bits admits small constant‑depth circuits using composite moduli: for any ε>0 there exists a modulus m so a depth‑3 mod‑m circuit has size exp(n^ε), and concretely the construction yields a mod-5 ∘ mod-6 ∘ mod-5 depth‑3 circuit of size exp(n^{1/3}) computing exact‑majority. Proof uses Lucas theorem and elementary symmetric polynomials combined by the Chinese remainder theorem, then removes AND layers via linearization (Chen–Papakonstantinou). More generally, with a modulus having R distinct prime factors and depth D the size is exp(n^{1/(R+D−3)}), and allowing AC0 gates improves constants and gives multiplicative R·D dependence.

AI-written summary · about

" chapters (6)

1. 0:00Start
2. 0:15Introduction: MOD gate
3. 0:37Introduction: ACC
4. 3:15Results: Smaller MOD circuits
5. 5:19Results: Even smaller circuits in ACC
6. 6:17Intuition