线性阈值函数的低权重近似与计算复杂度应用

"这篇论文探讨了线性阈值函数（Linear Threshold Function，LTF）的低权近似问题以及它们在计算复杂度理论中的应用。作者提出了一种构造方法，可以为任何给定的线性阈值函数找到一个低权重的近似函数，最多在1/4的输入上与原函数不一致。此外，还讨论了限制性注意力集中框架下学习线性阈值函数的样本数量的多项式界限。" 线性阈值函数是布尔函数的一种，通常表示为f(x) = sgn(n∑i=1wixi - θ)，其中w是权重向量，x是输入向量，θ是阈值，sgn是符号函数。这种函数在理论计算机科学中有广泛的应用，特别是在复杂性理论中，例如定义某些计算复杂度类如TC0。 论文的核心贡献在于展示了如何构建一个低权重的近似器g，它在最多1/4的输入上与原始函数f不一致。这提供了一个有效的近似方法，对于理解和分析线性阈值函数的性质和计算能力具有重要意义。此外，文中还证明了存在一个下界，即近似特定线性阈值函数所需的权重至少与n有关。 论文的第一个应用是展示了一个确定性的算法，该算法能在多项式时间内近似求解零-一背包问题的分配分数。虽然这个算法在n的对数方面有指数级的运行时间，但它仍为解决实际问题提供了新的视角。 第二个应用则涉及Chow参数，即线性阈值函数的0阶和1阶傅立叶系数。作者证明，任何线性阈值函数可以通过其Chow参数的估计来近似，精确度达到加性1/(n^2O(1/2))。这个结果首次给出了在“限制性注意力集中”框架内学习线性阈值函数所需的样本数量的多项式界。 论文的关键词包括布尔函数、线性阈值函数、Chow参数和计算学习理论，反映了研究的主要领域。主题分类涵盖了组合优化、几何学、计算复杂度等多个子领域，显示出线性阈值函数在这些领域都有重要应用。 这篇论文深入探讨了线性阈值函数的理论和应用，对于理解它们的计算复杂度和学习性具有重要价值，同时为实际问题的解决提供了新的工具和方法。