Fooling polytopes.
R. O'Donnell and R. Servedio and L.-Y. Tan.
J. ACM 69(2): 9:1-9:37, 2022.
Preliminary version in 51st Annual Symposium on Theory of Computing (STOC), 2019, pp. 614-625.


Abstract:

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

Link to full version


Back to main papers page