Randomness Buys Depth for Approximate Counting

DOI10.1109/FOCS.2011.19MaRDI QIDQ5494967zbMATH OpenFDO

Authors Emanuele Viola

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2011.19

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cited in

(4)

• On extracting space-bounded Kolmogorov complexity
• On the optimal compression of sets in PSPACE
• Size bounds on low depth circuits for promise majority
• \(\mathrm{BPL}\subseteq\mathrm{L}\text{-}\mathrm{AC}^1\)

This page was built for publication: Randomness Buys Depth for Approximate Counting

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