Efficient deterministic approximate counting for low-degree polynomial threshold functions

Anindya De, Rocco A. Servedio

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

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 ℝn and a parameter ε > 0, our algorithm approximates Prx∼{-1,1}n[p(x) ≥ 0] 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 nO d,c(1)ε-c 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(x 1,. ., xn) over {-1, 1}n, a positive integer κ and an error parameter ε, output a (1±ε)- multiplicatively accurate estimate to Ex∼{-1,1} n[|p(x)|κ]. Our algorithm runs in time O d,ε,κ (1) · poly(nd).

Original languageEnglish (US)
Title of host publicationSTOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages832-841
Number of pages10
ISBN (Print)9781450327107
DOIs
StatePublished - 2014
Event4th Annual ACM Symposium on Theory of Computing, STOC 2014 - New York, NY, United States
Duration: May 31 2014Jun 3 2014

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other4th Annual ACM Symposium on Theory of Computing, STOC 2014
CountryUnited States
CityNew York, NY
Period5/31/146/3/14

Keywords

  • Approximate counting
  • Derandomization
  • Polynomial threshold function

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Efficient deterministic approximate counting for low-degree polynomial threshold functions'. Together they form a unique fingerprint.

Cite this