Efficient deterministic approximate counting for low-degree polynomial threshold functions

Anindya De, Rocco Servedio

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_1,…