Satisfiability Algorithms II
summary
Proves nonconstructive lower bounds showing most degree‑2 GF(2) polynomials need size 2^{n−o(n)} for depth‑3 circuits when bottom fan‑in k = o(log n), combining VC‑dimension counting (probability a random degree‑2 polynomial is constant on a shattered set ≤ 2^{−d^2}) with a specification lemma that writes any k‑CNF as a union of linear‑frequency k‑CNFs (reducing cases to ~2^{O(n log n)}). Develops an extended switching lemma and joint canonical decision trees to get a randomized SAT algorithm running in time ~2^{n(1−μ)} with μ ≈ 1/(log c)^{d−1}, and an exponentially small parity correlation bound.
AI-written summary · about
chapters (10)
- 0:00Start
- 12:07How to Prove Stronger Lower Bounds for Depth-3 Circuits
- 15:41Sparsification Lemma
- 32:27Small Depth Circuits and Satisfiability Algorithm
- 37:33Correlation Bounds for Small Depth Circuits
- 38:22Further Improvements could be Hard
- 46:10Canonical Decision Tree for a Sequence of Formulas
- 47:55Extended Switching Lemma
- 50:20Switching Algorithm
- 52:17Algorithm for Depth-3 Circuits
related talks
31mFaster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC^0[p]
29mImproved Deterministic Algorithms for Sparse Max-SAT
25mLower Bounds for Problems Parameterized by Clique-width
17mSatisfiability Algorithms Based on Concentrated Shrinkage
23mTowards General and Tight Hardness Results for Graph Problems
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
10mQuery, Communication and Discrepancy
51mAn Improved Bound for Regular Partitions of Hypergraph of Bounded VC_2 Dimension