New Techniques For Proving Fine-Grained Average-Case Hardness
summary
A framework shows that if a worst‑case problem P equals a good low‑degree polynomial on {0,1} inputs (degree ≲ log n / log log n) and that polynomial is strongly D‑partite, then worst‑case hardness (from SETH, 3SUM, APSP) transfers to uniform average‑case hardness after a bitwise expansion of finite‑field evaluations; the reduction uses bit decompositions (≈ log n^O(k^2) instances) and polynomial‑interpolation error correction (univariate G of degree ≤2d, needs ~2/3 good points), so average solvers with 1−1/poly success imply subpolynomial overhead only.
AI-written summary · about
chapters (25)
- 0:00Intro
- 0:57What is finegrain complexity
- 1:39Our goal
- 1:57What does this look like
- 2:23Important note
- 2:43Randomized algorithms
- 2:58Worstcase matrix multiplication
- 5:13Factored Problems
- 5:43Story
- 6:07Core Problems
- 7:29Fun Problems
- 8:42Orthogonal Vectors
- 9:21Functions
- 10:26Why do we care
- 11:59Back to 0
- 15:22Bitwise Multiplication
- 16:48Cake Leaks
- 20:18Cake League Problem
- 24:21Volatile 2017 Paper
- 31:11Results
- 32:07Other Papers
- 33:07Factoring Problems
- 39:01Internals
- 39:25Polynomials
- 41:09Conclusion
related talks
48mUnstructured Hardness to Average-Case Randomness
01h 00mAverage-case Complexity for Polynomials, and All That
01h 11mPedagogical Talk: Failure of Low-Degree Polynomials
19mCounterexamples to the Low-Degree Conjecture
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials
50mAlgorithmic Regularity for Polynomials and Applications
39mAbove Average-Case Analysis?
01h 12mPedagogical Talk: Frameworks for Information-Computation Tradeoffs