Algorithms and Lower Bounds for Comparator Circuits from Shrinkage

on YouTube ↗19m

" summary

Proves an average-case lower bound: there is an explicit polynomial-time function f on n bits such that every comparator circuit with at most n^{1.5} gates agrees with f on at most 1/2 + 2^{-k} of inputs for k ≥ log n, matching prior worst-case bounds. Gives a nontrivial counting-SAT algorithm for size-n^{1.5} comparator circuits (runtime 2^n divided by a superpolynomial factor when k = ω(log n)), a pseudorandom generator that fools size-S circuits, an MCSP lower bound, and a new shrinkage-based wire-to-gate reduction plus a conversion data structure used in the algorithms.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 2:14Circuit complexity
3. 4:42The power of comparator circuits
4. 8:14Lower bounds for comparator circuits
5. 9:20Our results
6. 10:02Average-case lower bound
7. 11:32Circuit analysis algorithms: #SAT
8. 13:09Circuit analysis algorithms: PRGS
9. 15:22Techniques
10. 16:08Shrinkage for comparator circuits
11. 17:40Open problems

" related talks

• 16mOn Oracles and Algorithmic Methods for Proving Lower BoundsRyan Williams, Nikhil Vyas · ITCS 2023
• 01h 01mTop-Down Lower Bounds for Depth-Four CircuitsMika Göös · Structural Results 2023
• 17mSatisfiability Algorithms Based on Concentrated ShrinkageRuiwen Chen · Connections Between Algorithm Design and Complexity Theory
• 21mEfficiently Testable CircuitsMirza Ahad Baig, Suvradip Chakraborty, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej, Krzysztof Pietrzak · ITCS 2023
• 47mHardness Amplification and the Approximate Degree of Constant-Depth CircuitsJustin Thaler · Neo-Classical Methods in Discrete Analysis 2013
• 55mNon-commutative ComputationAvi Wigderson · Neo-Classical Methods in Discrete Analysis 2013
• 22mNew Lower Bounds and Derandomization for ACC, and a...Lijie Chen · ITCS 2023
• 32mA Finite Alternation Result for Reversible Boolean CircuitsPeter Selinger · Symmetry, Logic, Computation 2016