Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
summary
Presents the first unconditional FP^NP algorithm for ACC^0-Avoid and also gives FP^NP procedures for ACC^0-Remote-Point and ACC^0-Partial-AvgHard with quasi-polynomial stretch, using reductions to a new nontrivial algorithmic primitive: C-Satisfying-Pairs. The core tools are nonuniform satisfying-pairs algorithms plus a new short, smooth, rectangular PCP of Proximity; results run with an NP oracle, work unconditionally for ACC^0, and immediately recover the best known ACC^0 lower bounds.
AI-written summary · about
chapters (13)
- 0:00Intro
- 1:25Task: Prove a Lower Bound for CNF!
- 4:31Hard Partial Truth Tables...
- 10:57The Empty Pigeonhole Principle
- 11:47Range Avoidance Problem: Finding an Empty Hole?
- 13:28From Hard Partial Truth Table to Range Avoidance
- 15:14Explicit Constructions
- 17:25Circuit Lower Bounds via "Algorithmic Method"
- 19:52Circuit Lower Bounds Range Avoidance for Truth Table Generator
- 22:35RSW22: Algorithmic Method for Range Avoidance
- 25:18Comparison with the Algorithmic Method
- 28:03Range Avoidance from Satisfying-Pairs
- 34:26Open Problem: NC°-Avoid
related talks
22mNew Lower Bounds and Derandomization for ACC, and a...
01h 30mInapproximability of Constraint Satisfaction Problems II
01h 25mInapproximability of Constraint Satisfaction Problems IV
48mUnprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
01h 17mInapproximability of Constraint Satisfaction Problems V
01h 17mInapproximability of Constraint Satisfaction Problems III
56mApproximate Counting II
47mHardness Amplification and the Approximate Degree of Constant-Depth Circuits