Fall 2013

Deterministic Counting of Satisfying Assignments for Juntas of Degree-2 PTFs

Wednesday, Aug. 28, 2013 1:45 pm2:30 pm

Add to Calendar

We present a deterministic algorithm to epsilon-approximately count the number of satisfying assignments of a k-junta of degree-2 PTFs with a running time of poly(n). exp(k,epsilon). In particular, the algorithm has a poly(n) running time for slightly superconstant k and subconstant eps. It is a significant extension of a recent result on deterministic counting for degree-2 PTFs and is based on using multidimensional CLTs for gaussian polynomials derived from a combination of Stein's method and Malliavin calculus. Also, it provides the first instance of a deterministic poly-time counting algorithm for a non-trivial class of depth-3 circuits.