Efficient deterministic approximate counting for low-degree polynomial threshold functions
Efficient deterministic approximate counting for low-degree polynomial threshold functions
复制标题
低次多项式阈值函数的高效确定性近似计数
DOI：
10.1145/2591796.2591800
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Rocco A. Servedio
中科院分区：
文献类型：
--
作者：
Anindya De;Rocco A. Servedio
我们给出了确定性算法，用于近似计数的满意度分配（ptf）。在时间OD中的额外±ε中，ε（1）·Poly（ND）（由于NP- hard是NP-HARD，以确定上述概率是否为零即使对于随机算法，当然不可能。基于用于DEM-D PTFS的无条件伪和发电机的结构，用于所有C> 0的时间[等式]。这项工作的关键新颖技术贡献是•新的多元中心限制定理使用Malliavin Colculus和Stein方法的工具提供了这种新的CLT。多项式在高斯输入上。多项式多项式所有这些都具有极小的特征值。 ）为了将原始的近似计数问题降低到boolean hypercube作为我们结果的应用。以下时刻近似问题的可处理算法：给定{-1、1} n上的度d多项式p（x1，...，xn），一个正整数k和一个误差参数ε，输出a（1±± ε） - 多精确地估计[方程]。
We give a deterministic algorithm for approximately counting satisfying assignments of a degree-d polynomial threshold function (PTF). Given a degree-d input polynomial p(x) over Rn and a parameter ε > 0, our algorithm approximates Pr [EQUATION] to within an additive ±ε in time Od,ε(1) · poly(nd). (Since it is NP-hard to determine whether the above probability is nonzero, any sort of efficient multiplicative approximation is almost certainly impossible even for randomized algorithms.) Note that the running time of our algorithm (as a function of nd, the number of coefficients of a degree-d PTF) is a fixed polynomial. The fastest previous algorithm for this problem [Kan12b], based on constructions of unconditional pseudorandom generators for degree-d PTFs, runs in time [EQUATION] for all c > 0. The key novel technical contributions of this work are • A new multivariate central limit theorem, proved using tools from Malliavin calculus and Stein's Method. This new CLT shows that any collection of Gaussian polynomials with small eigenvalues must have a joint distribution which is very close to a multidimensional Gaussian distribution. • A new decomposition of low-degree multilinear polynomials over Gaussian inputs. Roughly speaking we show that (up to some small error) any such polynomial can be decomposed into a bounded number of multilinear polynomials all of which have extremely small eigenvalues. We use these new ingredients to give a deterministic algorithm for a Gaussian-space version of the approximate counting problem, and then employ standard techniques for working with low-degree PTFs (invariance principles and regularity lemmas) to reduce the original approximate counting problem over the Boolean hypercube to the Gaussian version. As an application of our result, we give the first deterministic fixed-parameter tractable algorithm for the following moment approximation problem: given a degree-d polynomial p(x1,..., xn) over {--1, 1}n, a positive integer k and an error parameter ε, output a (1±ε)-multiplicatively accurate estimate to [EQUATION]. Our algorithm runs in time Od,ε,k(1) · poly(nd).