六人团队证明多项式指数相关性界,攻克电路复杂性多个长期难题
Pooyahat · x · 2026-10-14
Pooya Hatami 与 Eshan Chattopadhyay、Chin Ho Lee、Shachar Lovett、Avishay Tal、Emanuele Viola 在 ECCC 发布论文修订版《Exponential Correlation Bounds for Polynomials》。
- 核心结果：不相交比特块上 k 个多数函数的 XOR，与任意域上任意布尔值 d 次多项式的相关性至多为 (4d/√ℓ)^k。
- 由此构造出种子长度为 d²·polylog(n/ε) 的显式伪随机生成器，可骗过 n 比特输入上的此类多项式。
- 结果进一步扩展到小规模 AC⁰[q] 电路（q 为任意固定素数幂）。
- 论文称这些结果解决了电路复杂性与伪随机性领域的多个长期悬而未决的问题。
- 修订版将主定理从 F₂ 推广到所有有限域，补充了新应用并扩写了论述。
「研究」频道最新
- arXiv 论文为 StopGrad 正名：无损失函数也能收敛到正确解 — srush_nlp · 2026-10-23
- PEARL 演示：LLM 机器人自主核对实验结果、修正方案并复测 — KevinKaichuang · 2026-10-23
- 伯克利 StyleStream 2.0：流式语音转换延迟降至 520ms 提速一倍 — Berkeley · 2026-10-23
- 数学博士生宣布离开学术界：AI 正让数学变得面目全非 — pickover · 2026-10-23
- ICLR 投稿现 LLM 残留自评：作者模型自曝结果不显著 — _onionesque · 2026-10-23
- AKV 推理系统让 Agent 自管 KV 缓存,成本降 27.7% 准确率反升 — _akhaliq · 2026-10-23