Probability Seminar: Ryan O'Donnell

  • Date: 04/10/2019
  • Time: 15:00
Lecturer(s):
Ryan O'Donnell, CMU
Location: 

University of British Columbia

Topic: 

Fooling Polytopes

Description: 

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)

Other Information: 

Location: MATH 126