n维线性阈值函数的高效逼近与最简表达

本文主要探讨的是n维线性阈值函数在计算机科学中的逼近问题，特别是针对布尔超立方体上的线性阈值函数f(x) = sign(w·x - θ)的研究。作者在纽约哥伦比亚大学的罗科A·计算机科学系和Ilias合作，他们的研究成果发表于2018年10月。 首先，文章的核心贡献是指数性地锐化了Friedgut的著名定理。Friedgut的定理指出，任何布尔函数f可以通过依赖于其总影响Inf(f)和维度n的系数2^O(Inf(f)/n)个变量来近似表示为一个阈值函数。作者在此基础上进一步证明，对于任意线性阈值函数f，只需要Inf(f)^2·poly(1/n)的变量就足够提供一个近似的n-接近阈值函数。这意味着上界被大大缩小，只需要比原定数量更少的变量即可达到高精度的逼近。 其次，文章还提出了第二个关键结果，即每个n元线性阈值函数可以被n-接近地表示为一个具有最小阈值(n)·2^O(1/n)的最小子函数。这相对于早期的[Ser07]中λ依赖性的改进显著，原结果中λ的依赖项是p(n)·2^O(λ/(λ^2))。作者使用了一种新的改进技术，即概率论中的强反集中界限，这种技术不仅简化了[Ser07]的证明过程，而且使近似阈值函数的分析范围超越了均匀分布假设，适用于低权重情况。 这项工作的初步成果曾在第24届IEEE计算复杂性年会上发表，并受到NSF等多个机构的资助。研究的深入展示了线性阈值函数在理论计算机科学中的核心地位，特别是在布尔函数逼近和复杂性分析方面。通过这些成果，作者们揭示了线性阈值函数的结构特性，并为进一步的理论研究提供了强有力的支持。