Lower Bounds for Unrestricted Boolean Circuits: Open Problems

on YouTube ↗31m

" summary

Current best unconditional lower bound for unrestricted Boolean circuits uses the gate elimination method to get roughly 3n gates by plugging an affine disperser for sublinear dimension (nonconstant on every affine subspace of dimension ~√n) and showing an affine substitution kills ~3+1/86 gates; a quadratic-variety variant nudges that to ~3.1n. Open specifics: no proof that an explicit affine disperser needs superlinear circuits (candidate constructions may have circuits ~n^3), gate-elimination cannot exceed 5n on some constructions, and non-gate-elimination routes (reconstruction, high out-degree counting, SAT-algorithm-to-lower-bound reductions, Valiant depth-3 reductions) so far fail to break linearity.

AI-written summary · about

" chapters (10)

1. 0:00Intro
2. 0:39Unrestricted Boolean Binary Circuits
3. 6:14Linear Size Circuits for Affine Dispersers
4. 8:53Limitations of Gate Elimination Informally: Gate elimination proofs are tedious and usually consist of a long case analysis. It is difficult to imagine a relatively
5. 13:18Multi-Output Functions Computing several functions simultaneously is definitely not easier than computing any one of them
6. 16:22Other Lower Bounds Essentially, just a few and, alas, none of them is currently known to give a stronger than 2n lower bound
7. 19:13Satisfiability Algorithms Faster than brute force search satisfiability algorithms imply circuit lower bounds [11]
8. 22:22Mass Production Effect We say that a mass production effect occurs when two copies of g can be computed by a circuit of size (much) smaller than 20g
9. 25:24Logarithmic Depth Circuits Alas, currently, it is not known
10. 27:29Converting Small Size Circuits into Non-trivial Depth 3 Formulas