Shrinkage under random projections, and cubic formula lower bounds in AC^0

on YouTube ↗23m

" summary

Proves an n^3 lower bound on De Morgan formula size for an explicit AC^0 function built by composing a small hard gadget F0 with a surjectivity block, using carefully designed random projections (not standard restrictions). Shows any formula shrinks by about the Korobchenko/adversary measure of G under these projections, so size(F∘G) ≥ size(F)·(adv(G))^2, recovering parity and giving a concrete AC^0 example where random-projection shrinkage works.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 0:22Formula Size / Depth
3. 1:47Motivation: Parallel Computation What is the power of Parallel Computation? Can we solve any problem a 1000 times faster with 1000 cores?
4. 2:56Belief vs. Proof We believe that some problems in P require exponential formula size.
5. 3:29Formula Size of Composition
6. 6:59Andreev's construction
7. 8:19Top-Down versus Bottom-Up Technique
8. 11:08Candidate Problem
9. 13:14The construction AC variant of Andreev's function
10. 14:54An nº formula size lower bound for AC
11. 18:21A bit about the techniques