# Efficient deterministic approximate counting for low-degree polynomial threshold functions

arXiv: https://arxiv.org/abs/1311.7178 · HTML: https://mlsanity.com/paper/1311.7178/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Nov 2013.

## Built on by (most cited first, 2 of 2)

- [Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs](https://mlsanity.com/paper/2404.00529/) (2024)
- [PTF Testing Lower Bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2511.19398/) (2025)

## Abstract (arXiv)

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(x1,dots,xn) over Rn and a parameter ε> 0, our algorithm approximates Pr_x ~ -1,1n[p(x) ≥ 0] to within an additive ± ε in time Od,ε(1)· mathoppoly(nd). (Any sort of efficient multiplicative approximation is impossible even for randomized algorithms assuming NPnot=RP.) 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 (due to Kane), based on constructions of unconditional pseudorandom generators for degree-d PTFs, runs in time n^Od,c(1) · ε-c for all c > 0. The key novel 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.