Something about new average-case hard problems?
summary
Tutorial-style exposition of the low-degree polynomials model uses the sum of squared low-degree Fourier/Hermite coefficients — called the low-degree chi-squared — to predict when hypothesis-testing problems resist polynomial-time attacks. Concrete cases: planted clique and sparse parity fit the framework; tensor PCA shows thresholds (claims: information-theoretic recovery above √n, believed hard below n^{3/4}, best algorithms are subexponential in the intermediate regime). Method captures spectral and subgraph-counting attacks and rules out SQ algorithms, but ignores algebraic attacks and needs product-Q or permutation-symmetric P plus post-noise.
AI-written summary · about
chapters (12)
- 0:00Average-case hardness overview
- 1:05Low-degree method basics
- 4:11Null versus planted testing
- 7:47Planted clique examples
- 10:44Learning parity with noise
- 18:17Tensor PCA hardness
- 28:36Low-degree polynomial model
- 34:06Low-degree heuristic optimization
- 42:22Chi-squared divergence computation
- 47:11Implications for SQ and SOS
- 53:40Cryptography applications
- 1:03:20Discussion on one-way functions and future directions
related talks
37mAlgebraic Algorithms for LWE
51mMultilinear Maps and Attacks II
41mReducibility and Statistical-Computational Gaps from Secret Leakage
40mA Duality Between One-Way Functions and Average-Case Symmetry of Information
01h 40mHistorical Talk on Lattice-Based Cryptography
46mCryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
01h 04mHow to Encrypt a Functionality