Pseudorandom generators for combinatorial shapes

DOI10.1145/1993636.1993671zbMath1288.68226OpenAlexW2006007166MaRDI QIDQ5419095

Raghu Meka, David Zuckerman, Omer Reingold, Parikshit Gopalan

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1993636.1993671

zbMATH Keywords

limit theoremspseudorandom generatorsbranching programssmall space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

DNF sparsification and a faster deterministic counting algorithm ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Unnamed Item