线性阈值函数的高效逼近与应用

"这篇论文探讨了线性阈值函数的逼近方法及其在计算科学中的应用，特别是关注在布尔超立方体上的线性阈值函数。文章由纽约哥伦比亚大学的学者撰写，涉及领域包括计算科学、阈值函数、逼近理论以及概率论。作者通过两个主要成果展示了如何使用简单阈值函数逼近n维布尔超立方体上的任意线性阈值函数。 首先，论文揭示了一个关键结果，即任何n元线性阈值函数f可以被一个仅依赖于Inf(f)的2·poly(1/n)个变量的简单阈值函数以n-接近的方式逼近。Inf(f)表示函数f的总影响或平均灵敏度。这一发现是对Friedgut定理的指数增强，该定理指出，布尔函数可以用2O(Inf(f)/n)个变量的函数进行计算。此外，论文还给出下界，证明需要依赖于Inf(f)^2+1/Inf(f)^2数量的变量来实现$f$的$\epsilon$-近似。 其次，论文证明了每个n元线性阈值函数都可以被一个具有最小阈值(n)·2O(1/n)的最小阈值函数以n-接近的方式逼近。这在误差参数λ的依赖性上是一个显著改进，优于之前[Ser07]中λ=p(n)·2O(1/λ^2)的界限。新方法利用概率论中的强反集中界限，提供了一个更简单和模块化的证明，并且能够扩展到非均匀分布的低权重近似阈值函数。 这项研究的早期版本曾在第24届IEEE计算复杂性年会上发表，且得到了多项基金会的资金支持，包括NSF和DARPA。论文的贡献不仅在于对现有理论的改进，还在于引入了一种新的分析技术，这对于理解和处理线性阈值函数以及相关的布尔函数问题具有重要意义。" 这篇论文的核心知识点包括： 1. 线性阈值函数的定义和它们在计算科学中的重要性。 2. 总影响（Inf(f)）和平均灵敏度的概念，以及它们在函数逼近中的角色。 3. Friedgut定理的概述及其在函数逼近中的应用。 4. 提出的新上界和下界，关于逼近线性阈值函数所需的变量数量。 5. 对λ参数依赖性的改进，以及与之前工作[Ser07]的比较。 6. 使用概率论中的强反集中界限作为分析工具。 7. 结果的实用性和对非均匀分布情况的扩展。 这些知识点对于深入理解线性阈值函数的理论性质和实际应用，特别是在计算复杂性理论、布尔函数分析和机器学习等领域具有重要价值。