Errorless versus Error-prone Average-Case Complexity

on YouTube ↗15m

" summary

Paper proves reductions between error-prone heuristics and errorless average-case algorithms by building on non-adaptive average BPP/poly instant checker machinery and a conversion that answers a checker's queries with a Hur-P heuristic; shows unconditional equivalence for P and for UP ∩ co-UP; gives a construction of a weaker BPP instant checker for NP and a pseudo-extending construction that turns a hitting-set generator with seed length n−1 into PRGs, reducing seed to n^ε for any constant ε; several open gates remain.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 0:11Errorless vs. Error-prone Heuristics The theory of average-case complexity studies a distributional problem (CD).
3. 4:12Key Insight: Connection to Instance Checker [Blum-Kannan 95]
4. 6:05Equivalence If we consider an average-case version of an instance checker in a non-uniform setting, we get an exact equivalence.
5. 7:56Unconditional Results
6. 9:03PRG versus HSG We use our results to show some equivalence between a pseudorandom generator (PRG) and a hitting set generator (HSG).
7. 10:38Proof Sketch: Instance Checker to Errorless-to-Error-prone Reduction
8. 14:07Conclusion