Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
summary
Shows a lossless linear-program dual view using dual LP / dual polynomials to prove approximate-degree lower bounds, with an explicit combining trick (feed sign(inner) into outer and multiply magnitudes) borrowed from Sher–Lee. Introduces one-sided approximate degree, proves OR of T copies preserves one-sided degree d even for error 1 − 2^{-Ω(T)}, and uses element-distinctness (one-sided degree ≈ n^{2/3}) to build AC0 functions with one-sided degree ≈ n^{2/5} and discrepancy 2^{-n^{2/5}} (depth 4). Gives near-tight depth-3 OR-tree lower bound ≈ n^{1/2}; mentions stronger threshold-degree bounds for depth-k.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:30Boolean Functions
- 2:41Example: What is the Approximate Degree of AND.?
- 6:11Beyond Symmetrization
- 7:23History of the OR-AND Tree
- 8:12Linear Programming Formulation of Approacimate Degree
- 9:44Dual Characterization of Approximate Degree
- 11:45Constructing a Dual Polynomial
- 14:41Pure High Degree Analysis She09
- 20:05Summary of Correlation Analysis
- 20:29One Sided Approacimate Degree
- 21:31Dual Formulation of odeg
- 25:02Proof of Main Theorem: Pure High Degree
- 25:36Proof of Main Theorem: Correlation Analysis
- 27:29A New odeg Bound for AC
- 29:46New Lower Bounds for AC
- 32:59Back to OR-AND Trees
- 35:04First Proof Attempt for the case
- 37:38Threshold Degree of AC
related talks
01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders
01h 01mTop-Down Lower Bounds for Depth-Four Circuits
16mOn Oracles and Algorithmic Methods for Proving Lower Bounds
26mOn the Intersection of a Sparse Curve and a Low-degree Curve: A Polynomial Version of the Lost Theor
51mOn constant T-depth circuits
01h 01mTrue Complexity of Multilinear Systems
29mApproximating the Permanent of Positive Semidefinite Matrices
53mNew Lower Bounds and Derandomization for ACC, and a...