色编码技巧突破:对称布尔函数获 2^O(√n) 深度-3 电路
rrwilliams · x · 2026-09-30
计算复杂度理论迎来一个出人意料的结果:借助组合数学中的 Alon-Yuster-Zwick 色编码（color coding）技巧，每个对称布尔函数都可以用大小为 2^{O(√n)} 的深度-3 AC 电路实现。
发帖人 Ryan Williams 感叹这是「电路下界难证是因为下界本来就是假的」这一说法的最新例证——上界结果一次比一次小，说明我们此前对电路能力的直觉可能系统性偏保守。
所属事件:色编码技巧突破：对称布尔函数获深度-3 小电路(2 条相关)→
「研究」频道最新
- 0.6B 小模型替换规则清洗栈,预训练 DCLM 分数提升 4.7% — XiongChenyan · 2026-09-30
- 微软研究:六个主流 LLM 编程时也存在达克效应式自信偏差 — burkov · 2026-09-30
- PixAI 发布动漫基础模型 Tsubaki.3,开源 Tagger 并发布技术报告 — Level-Ninja-2492 · 2026-09-30
- Lean 之父 de Moura 谈 AI 证明:绿勾也会骗人,Collatz 事件暴露内核漏洞 — Machine Learning Street Talk · 2026-09-30
- 论文 LLM-42 登 SOSP 2026:验证式投机让 LLM 推理确定性几乎零开销 — tianyin_xu · 2026-09-30
- 前沿模型能力全是锯齿：平均分第一也不代表能随便换用 — vsikka · 2026-09-30