Deterministic approximate counting of polynomial threshold functions via a derandomized regularity lemma.
R. Servedio and L.-Y. Tan.
25rd International Workshop on Randomness and Computation (RANDOM), 2021, pp. 37:1-37:18.


Abstract:

We study the problem of deterministically approximating the number of satisfying assignments of a polynomial threshold function (PTF) over Boolean space. We present and analyze a scheme for transforming such algorithms for PTFs over Gaussian space into algorithms for the more challenging and more standard setting of Boolean space. Applying this transformation to existing algorithms for Gaussian space leads to new algorithms for Boolean space that improve on prior state-of-the-art results due to Meka and Zuckerman [Meka and Zuckerman, 2013] and Kane [Kane, 2012]. Our approach is based on a bias-preserving derandomization of Meka and Zuckerman's regularity lemma for polynomials [Meka and Zuckerman, 2013] using the [Servedio and Tan, 2018] pseudorandom generator for PTFs.

Link to conference version


Back to main papers page