多项式与有理函数逼近的最优半空间:打破通信复杂度界限
83 浏览量
更新于2024-06-17
收藏 1.14MB PDF 举报
本文主要探讨的是"最难的半空间"的逼近问题,特别是在多项式和有理函数的背景下。作者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基金会提供的支持,并列出了参考文献,供后续研究者进一步探索相关领域。
这篇论文不仅解决了关于半空间逼近的难题,还推动了通信复杂性和计算学习领域内的理论进展,展示了作者在这些领域的深厚学术造诣。
2021-06-08 上传
2021-10-04 上传
2019-06-10 上传
2023-05-20 上传
2023-09-26 上传
2023-04-05 上传
2023-07-29 上传
2023-10-23 上传
2023-05-30 上传
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 5
- 资源: 2万+
最新资源
- Hadoop生态系统与MapReduce详解
- MDS系列三相整流桥模块技术规格与特性
- MFC编程:指针与句柄获取全面解析
- LM06:多模4G高速数据模块,支持GSM至TD-LTE
- 使用Gradle与Nexus构建私有仓库
- JAVA编程规范指南:命名规则与文件样式
- EMC VNX5500 存储系统日常维护指南
- 大数据驱动的互联网用户体验深度管理策略
- 改进型Booth算法:32位浮点阵列乘法器的高速设计与算法比较
- H3CNE网络认证重点知识整理
- Linux环境下MongoDB的详细安装教程
- 压缩文法的等价变换与多余规则删除
- BRMS入门指南:JBOSS安装与基础操作详解
- Win7环境下Android开发环境配置全攻略
- SHT10 C语言程序与LCD1602显示实例及精度校准
- 反垃圾邮件技术:现状与前景