Talks
Fall 2018

Fooling Polytopes
Wednesday, Sep. 12, 2018 12:00 pm – 12:45 pm PDT
Event:
Speaker:
Li-Yang Tan (Stanford University)
We give a pseudorandom generator that fools m-facet polytopes over {0,1}^n with seed length polylog(m) * 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.