Unstructured Hardness to Average-Case Randomness

on YouTube ↗48m

" summary

Proves that polynomial-time average-case derandomization of RP follows from concrete, weaker hardness hypotheses: e.g., any logspace-uniform family of circuits of size 2^{O(n)} and depth 2^{o(n)} that is hard for randomized algorithms running in time 2^{ε n} yields a deterministic poly-time algorithm correct on 1−1/n fraction of inputs; also shows the same derandomization from fine-grained assumptions such as counting k‑cliques requiring time n^{log(k)}. Key tools are a targeted hitting set generator, optimal worst‑to‑average reductions for linear space, and a tolerant instance checker*; derandomization is one‑sided (RP).

AI-written summary · about

" chapters (22)

1. 0:00Introduction
2. 2:05Motivation
3. 3:17Action Sequence
4. 6:35Outline
5. 7:15Classical Missing Piece
6. 7:30Classical Hardness vs Randomness
7. 7:40Exponential Time
8. 8:47Hardness vs Randomness
9. 9:53Uniform Setting
10. 10:46Technical Problem
11. 11:26Uniform Reconstruction
12. 11:46Classical Approach
13. 13:16Limitations of Classical Approach
14. 14:10Missing Piece
15. 17:38Motivation Question
16. 20:35Work Problemcentric Randomization
17. 23:16Special Case
18. 26:11Proof
19. 28:11Building Block
20. 32:32Polimorphic Encryption
21. 34:20Instance Tracker
22. 35:07Revised Approach

" related talks

• 44mNew Techniques For Proving Fine-Grained Average-Case HardnessAndrea Lincoln · Rigorous Evidence for Information-Computation Trade-offs
• 49mHard Languages in NP ∩ coNP and NIZK Proofs from Unstructured HardnessAmit Sahai, Alexis Korb · Minimal Complexity Assumptions for Cryptography 2023
• 58mSmoothed CSP Refutation Is As Easy As Random, For Both Efficient Algorithms And CertificatesPravesh K. Kothari · Rigorous Evidence for Information-Computation Trade-offs
• 24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin GlassesChris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi · ITCS 2023
• 40mClustering Under Perturbation ResilienceColin White · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 44mSomething for Almost Nothing: Advances in Sub-Linear Time AlgorithmsRonitt Rubinfeld · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 47mNatural Proofs in Algebraic Circuit ComplexityAnamay Tengse · Proof Complexity and Meta-Mathematics 2023
• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017