Counterexamples to the Low-Degree Conjecture
summary
Refutes Hopkins’ low-degree conjecture by building distributions where degree-O(log n) polynomials provably fail to distinguish IID Gaussian Q from structured P, yet a polynomial-time procedure distinguishes Q from a noisy P; key tools are an error-correcting code with d-wise independence and a binary expansion trick that packs codewords into real-valued entries so decoding survives limited noise. Also shows symmetry matters by giving a Bernoulli counterexample and recommends replacing resampling noise with small entrywise corruption.
AI-written summary · about
chapters (10)
- 0:00Start
- 0:15High Dimensional Testing Problems
- 3:19Low Degree Algorithms
- 3:29A Low Degree Algorithm
- 4:03What Does It Mean for Such a Polynomial To Succeed at Testing
- 7:48The Planted Three Xor Problem
- 10:38Symmetry Assumption
- 12:55Second Claim Which Is that the Symmetry Assumption Is Necessary
- 15:53Symmetric Distributions
- 17:37Erasure
related talks
01h 11mPedagogical Talk: Failure of Low-Degree Polynomials
29mComputational Barriers to Estimation from Low-Degree Polynomials
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials
01h 12mPedagogical Talk: Frameworks for Information-Computation Tradeoffs
01h 00mAverage-case Complexity for Polynomials, and All That
44mNew Techniques For Proving Fine-Grained Average-Case Hardness
57mStructure Of Boolean Almost Low Degree Functions On The Biased Cube
50mAlgorithmic Regularity for Polynomials and Applications