An SoS Entropy Dichotomy via Windowed Hypercontractivity
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918150401949696 |
|---|---|
| author | Lela, Marko |
| author_facet | Lela, Marko |
| contents | We prove an entropy versus degree dichotomy for low-degree tests and the Sum-of-Squares (SoS) hierarchy on a calibrated window after a gadget layer. For a target distribution \(μ\) and a product-like proxy \(u\), we study the low-degree discrepancy \(Δ_k(μ,u)\), defined as the optimal distinguishing advantage of degree \(\le k\) polynomial tests. Using a bias-orthonormal Walsh basis and a test-moment equivalence on the window, we relate \(Δ_k\) (up to constants) to the squared \(\ell_2\) mass of signed low-degree moments. Calibrated pseudoexpectations match \(u\) on all moments of degree \(\le k\), hence test discrepancy equals SoS pseudoexpectation deviation. Under bias, product, and width assumptions along a switching path, a windowed Bonami--Beckner inequality yields hypercontractive tail bounds. Combining these with moment matching, we obtain a discrepancy-to-degree theorem: if \(Δ_k(μ,u) \ge n^{-β}\), then any polynomial-calculus or SoS refutation separating \(μ\) from \(u\) requires degree \(Ω(k)\). Instantiating \(k = c \log n\) gives an explicit \(Ω(\log n)\) SoS degree lower bound whenever \(Δ_k \ge n^{-η}\). All constants are explicit and depend only on calibrated window parameters. This work provides the SoS/low-degree core and complements a prior calibration blueprint; a companion paper lifts the windowed statements to full distribution families. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_24280 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An SoS Entropy Dichotomy via Windowed Hypercontractivity Lela, Marko Computational Complexity Primary 68Q17, Secondary 03F20, 06E30, 68Q25 F.1.3; F.1.2; F.2.2; G.3 We prove an entropy versus degree dichotomy for low-degree tests and the Sum-of-Squares (SoS) hierarchy on a calibrated window after a gadget layer. For a target distribution \(μ\) and a product-like proxy \(u\), we study the low-degree discrepancy \(Δ_k(μ,u)\), defined as the optimal distinguishing advantage of degree \(\le k\) polynomial tests. Using a bias-orthonormal Walsh basis and a test-moment equivalence on the window, we relate \(Δ_k\) (up to constants) to the squared \(\ell_2\) mass of signed low-degree moments. Calibrated pseudoexpectations match \(u\) on all moments of degree \(\le k\), hence test discrepancy equals SoS pseudoexpectation deviation. Under bias, product, and width assumptions along a switching path, a windowed Bonami--Beckner inequality yields hypercontractive tail bounds. Combining these with moment matching, we obtain a discrepancy-to-degree theorem: if \(Δ_k(μ,u) \ge n^{-β}\), then any polynomial-calculus or SoS refutation separating \(μ\) from \(u\) requires degree \(Ω(k)\). Instantiating \(k = c \log n\) gives an explicit \(Ω(\log n)\) SoS degree lower bound whenever \(Δ_k \ge n^{-η}\). All constants are explicit and depend only on calibrated window parameters. This work provides the SoS/low-degree core and complements a prior calibration blueprint; a companion paper lifts the windowed statements to full distribution families. |
| title | An SoS Entropy Dichotomy via Windowed Hypercontractivity |
| topic | Computational Complexity Primary 68Q17, Secondary 03F20, 06E30, 68Q25 F.1.3; F.1.2; F.2.2; G.3 |
| url | https://arxiv.org/abs/2509.24280 |