Talks
Fall 2013
![](https://old.simons.berkeley.edu/sites/default/files/styles/workshop_main/public/programs/images/real_analysis_green_0.jpg?itok=tRAYtSkn)
Deterministic Counting of Satisfying Assignments for Juntas of Degree-2 PTFs
Wednesday, August 28th, 2013, 1:45 pm–2:30 pm
Speaker:
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.
Attachment | Size |
---|---|
![]() | 4.56 MB |