Circuit Complexity and Connections I
summary
Argues that small improvements in circuit algorithms yield provable lower bounds: a deterministic SAT speedup of roughly 2^n / n^10 already implies NEXP is not in P/poly, and even tiny improvements versus exhaustive search have nontrivial consequences. Uses derandomization, padding, reductions and polynomial identity testing as main tools; shows MCSP in P collapses randomness and yields explicit hard functions. Highlights startling facts like undecidable languages living in P/poly and an earlier result that some 700-bit instances require >10^80 gates.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:49Infinite Circuits
- 5:20Circuit Analysis Algorithms
- 12:43Linear Circuits
- 21:10Pseudorandom Generators
- 24:20Input Links
- 27:22Connections
- 27:38Algorithms
- 28:09Circuit Complexity
- 35:25Circuit Analysis
- 40:52Arithmetic Complexity
- 47:33Boolean
- 50:27Lower Bounds
related talks
01h 21mComputational Complexity in Theory and in Practice
35mSuperlinear Lower Bounds for Multipass Graph Processing
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
01h 05mGraph Algorithms in the MPC Model
29mImproved Deterministic Algorithms for Sparse Max-SAT
17mSatisfiability Algorithms Based on Concentrated Shrinkage
23mTowards General and Tight Hardness Results for Graph Problems
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems