Title: Deterministic Approximate Counting for Low-Degree Polynomial Threshold Functions
Speaker: Rocco Servedio, Columbia University
Date: Wednesday, April 13, 2016 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Consider the following algorithmic problem: You are given a degree-d real polynomial over n 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.
See: http://www.cs.rutgers.edu/~allender/theory-spring16.html