Fooling polytopes

Computer Science/Discrete Mathematics Seminar I
Topic:Fooling polytopes
Speaker:Li-Yang Tan
Affiliation:Stanford University
Date:Monday, April 1
Time/Room:11:00am - 12:00pm/Simonyi Hall 101
Video Link:

We give a pseudorandom generator that fools $m$-facet polytopes over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot \mathrm{log}(n)$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any $\{0,1\}$-integer program. Joint work with Ryan O'Donnell and Rocco Servedio.