通过半随机CSP反驳简化与奇阶情况实现Cell-Probe下界突破

近期工作（Korten、Pitassi与Impagliazzo，FOCS 2025）建立了静态数据结构下界、电路范围避免与伪随机CSP实例反驳之间的深刻联系，推动了Cell-Probe/比特探针模型中若干长期下界的改进。本文通过更简化的归约到XOR反驳方法，并结合奇阶情况处理，在特定情形下进一步改进了这些下界。我们的结果可视为对现有最先进半随机XOR反驳分析（Guruswami、Kothari与Manohar，STOC 2022；Hsieh、Kothari与Mohanty，SODA 2023）的完全去随机化，补充了Korten等人获得的偶阶情况去随机化。

作为主要技术陈述，我们证明：对于任何显著扩展输入的多输出常数深度电路，其输出极可能远离从具有充分独立性的分布中采样的字符串，且这一现象可被高效认证。通过视角的适当转换，这为Cell-Probe下界和电路范围避免算法提供了应用。

注释：欢迎评论

学科分类：计算复杂度（cs.CC）；密码学与安全（cs.CR）；数据结构与算法（cs.DS）

引用方式：arXiv:2507.22265 [cs.CC]
（或此版本 arXiv:2507.22265v1 [cs.CC]）

DOI：https://doi.org/10.48550/arXiv.2507.22265

提交历史：2025年7月29日 22:33:09 UTC（41 KB）