Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions

on YouTube ↗31m

" summary

Proves concrete average-case hardness from weaker worst-case fine‑grained assumptions: improving on Hirahara’s 2^{O(N/log N)} threshold, the paper shows that if UP requires >2^{O(√N log N)} worst‑case time then nondeterministic linear‑time problems are not solvable on average in quasi‑linear time (N·polylog N). Key tools are time‑bounded Kolmogorov complexity and a Shaltiel–Umans extractor plus time hierarchy + efficient PCPs; it also builds a PRG that fools T‑time, M‑advice distinguishers, computable in time T·poly(M), giving a low‑overhead derandomization that makes the reduction work.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:14P vs. NP and Cryptography
3. 1:20Impagliazzo's Five Worlds [Impagliazzo '95]
4. 3:43Some Complexity Background
5. 6:42Recent Progress [Hirahara, STOC '21]
6. 9:36What about weaker worst-case assumptions?
7. 12:36Another Interpretation: Fine-grained Complexity
8. 13:30"Fine-grained" Five Worlds
9. 14:27Meta-Complexity Background
10. 16:45Quick Overview of [Hirahara, '21] Framework
11. 18:06Quick Overview of Hirahara, '21 Framework (cont.)
12. 21:44Key Bottleneck in Improving Results
13. 23:38How do we get p(t) to grow slowly?
14. 25:54High-level Sketch of PRG Construction
15. 29:08Summary and Open Questions