多项式与有理函数逼近的最优半空间：打破通信复杂度界限

本文主要探讨的是"最难的半空间"的逼近问题，特别是在多项式和有理函数的背景下。作者Alexander A. Sherstov针对半空间h的0-1范数下界的逼近问题进行了深入研究，目标是找到一个具有挑战性的半空间，其多项式和有理函数逼近能够达到与平凡上界相匹配的最佳性能。这个问题的解决可以追溯到Myhill和Kautz于1961年的开创性工作。 论文的核心内容包括以下几个方面： 1. **最硬的半空间**：作者构建了一个特定的半空间，这个半空间对于多项式和有理函数的逼近具有独特的困难，即下界与上界相匹配，显示了理论上的最优特性。 2. **符号秩与通信复杂性**：研究结果被应用于通信复杂性理论，设计出一个通信问题，展示了符号秩与差异之间的最大可能分离，达到O(n)与2^n-n之间的差距，这相比于之前的结果有所提升，是对Babai, Frankl, and Simon (FOCS 1986)工作的优化。 3. **k-party number-on-the-forehead模型**：文章扩展到多党通信模型，证明了在该模型下，存在一个明确的分离，即log n与n/(4n)的通信与无界误差和弱无界误差之间的差距，进一步巩固了作者的研究成果。 4. **数学工具**：文中涉及了符号表示、矩阵分析、多项式和有理函数的逼近方法，以及与数论和通信复杂性相关的技术，如谨慎性和模式矩阵法。 5. **离散整数集的性质**：讨论了整数集合的离散性，包括基本属性、潜在界限和结构，这些都是构建最优逼近的关键步骤。 6. **单变量分析**：对单变量线性型的分布、愚弄分布以及单变量问题的简化进行了深入探讨，这些分析对于证明关键定理至关重要。 7. **主要成果**：论文详细阐述了多项式和有理函数逼近的具体结果，包括阈值度、阈值密度，以及它们如何影响通信复杂性，同时提出了循环膨胀器的概念。 8. **结论与致谢**：作者总结了研究成果，感谢NSFCAREER奖CCF-1149018和Alfred P. Sloan基金会提供的支持，并列出了参考文献，供后续研究者进一步探索相关领域。 这篇论文不仅解决了关于半空间逼近的难题，还推动了通信复杂性和计算学习领域内的理论进展，展示了作者在这些领域的深厚学术造诣。