Fooling polytopes

DOI10.1145/3313276.3316321MaRDI QIDQ5212803zbMATH OpenOpenAlexFDO

Authors Ryan O'Donnell, Li-Yang Tan, Rocco A. Servedio

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.04035

zbMATH Keywords

central limit theoremsderandomizationintersections of halfspacespolytopespseudorandom generators

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Randomized algorithms (68W20) Approximation algorithms (68W25) Analysis of algorithms (68W40) Integer programming (90C10)

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

Recommendations

• Fooling Polytopes
• Fooling sets and the spanning tree polytope
• Polyhedrality in pieces
• Polytopes
• scientific article; zbMATH DE number 1368684
• scientific article; zbMATH DE number 3944707
• Convex hulls of polyominoes
• scientific article; zbMATH DE number 5320559
• Polytopes and large counterexamples

Cited in

(6)

• Central limit theorem and bootstrap approximation in high dimensions: near \(1/\sqrt{n}\) rates via implicit smoothing
• Improved central limit theorem and bootstrap approximations in high dimensions
• Fooling Polytopes
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• Nearly optimal central limit theorem and bootstrap approximations in high dimensions
• Second- and higher-order Gaussian anticoncentration inequalities and error bounds in Slepian's comparison theorem

This page was built for publication: Fooling polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212803)