Probability Seminar: Ryan O'Donnell

We give a nearly efficient *deterministic* algorithm for approximately counting the number of 0/1-coordinate-points in high-dimensional polytopes.  The two main technical tools are: a new multidimensional Berry--Eseen theorem under limited independence; and, a new multidimensional Littlewood--Offord theorem for polytopes.

Joint work with Rocco Servedio (Columbia) and Li-Yang Tan (Stanford)