Derandomization to Boolean Circuit Lower Bounds
summary
Main claim: any general derandomization of probabilistic algorithms forces nontrivial nonuniform lower bounds, and conversely strong circuit lower bounds yield universal pseudorandom generators. Proof combines a Meyer-style uniform circuit encoding, PCP amplification to replace for-all checks by random sampling, and a shelf-collapsing win-win argument (Kannan/Shannon counting) that moves hardness down the exponential hierarchy. Concretely, showing CAPP ∈ P yields that NEXP ∩ coNEXP has no P/poly circuits, and variants use the easy-witness lemma and quantitative refinements for subexponential tradeoffs.
AI-written summary · about
chapters (9)
- 0:00Start
- 4:02Constructing a Pseudo-Random Generator
- 8:03General Rice's Theorem for Polynomial Time Computable Functions
- 24:10Circuit Approximation Proximate Probability Problem
- 26:07Argument for Shifting from the Non-Uniform Model to a Uniform Model from Connections between Non-Uniform Complexity in Uniform Complexity
- 29:16Uniform Circuit Representation
- 41:48The the Shelf Collapsing Argument
- 44:05Shelf Collapsing Argument
- 48:05The Shelf Collapse Argument
related talks
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
01h 03mBeyond Boolean Circuits in Garbled Circuits
29mAmplifying Contextual Distance in Higher-Order Languages, using the Law of Large Numbers
10mQuery, Communication and Discrepancy
24mVerifying Almost-Sure Termination for Randomized Distributed Algorithms
30mOn the Optimal Round Complexity of Multi-Party Computation in the Plain Model
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
31mParameterized Verification of Systems with Precise (0,1)-Counter Abstraction