Theory Seminar - Fooling Polytopes

Fooling Polytopes

Abstract: We give an explicit pseudorandom generator with seed length poly(log m, 1/\delta) * log n that \delta-fools the class of all m-facet polytopes over {0,1}^n. The previous best seed length had linear dependence on m. As a corollary, we obtain a deterministic quasipolynomial time algorithm for approximately counting the number of feasible solutions of general {0,1}-integer programs.

Joint work with Ryan O'Donnell (CMU) and Li-Yang Tan (Stanford).

Bio: Rocco Servedio is a professor and chair of the Department of Computer Science at Columbia University, where he does research in theoretical computer science.  His main research interests lie in computational complexity theory, computational learning theory, property testing, and the role of randomness in computation.