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: https://video.ias.edu/csdm/2019/0401-Li-YangTan

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.