Fooling Polytopes

08/13/2018
by   Ryan O'Donnell, et al.
0

We give a pseudorandom generator that fools m-facet polytopes over {0,1}^n with seed length polylog(m) · 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset