A Compression Algorithm for AC^0[p] Circuits Using Certifying Polynomials

on YouTube ↗49m

" summary

Algorithm compresses Boolean truth tables that have small AC^0[p] circuits into circuits of size about 2^n / m where m = exp(Ω(n / polylog n)) for constant depth and polynomial s, by building many low-degree certifying polynomials (degree ~ n/2 − n/polylog n) that are found by solving linear systems. It combines Razborov‑Smolensky style low‑degree approximations p with polynomials q vanishing on the approximation errors (final certificate = q·p), bounds the bad “forced points” set using a KneE and Wang extremal algebraic closure result, and outputs a working compressed circuit.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 0:36Meta-algorithmic problems
3. 2:29Compression Algorithm for a circuit class C
4. 7:05Compression problem for DNFS
5. 10:02Compression algorithms for other classes of circuits (Chen et al. (2014))
6. 15:43More general classes of circuits
7. 16:32Compression algorithms for ACP circuits
8. 17:35Polynomials and polynomial approximations
9. 19:26Razborov approximations to AC 2 circuits
10. 21:04Natural approach to compression problem
11. 24:22Certifying polynomials (ABFR '94, Green '95)
12. 28:47Finding Certifying polynomials
13. 31:52Using Vo to compress
14. 33:44Problems with the approach
15. 34:52Handling second issue
16. 36:35Overall approach summary
17. 37:44Constructing certifying polynomials
18. 40:44Bounding F
19. 42:12The problem and its solution
20. 46:28Open questions