Consider the following algorithmic problem: You are given a degree-d real polynomial over nn variables x1,...,xn. You would like to (approximately) compute the fraction of points in the Boolean hypercube {0,1}^n on which the polynomial takes a non-negative value. (Equivalently, you are given a degree-d polynomial threshold function, and you would like to approximately count its satisfying assignments.)

This problem is trivial to solve using random sampling...but what if you are not allowed to use randomness? In this talk we describe an efficient deterministic algorithm for this approximate counting problem. The algorithm employs many ingredients including invariance principles, new central limit theorems for low-degree polynomials, and new structural decompositions of such polynomials. No prior background will be assumed for the talk.

Joint work with Anindya De.