Randomness Buys Depth for Approximate Counting
From MaRDI portal
Publication:5494967
DOI10.1109/FOCS.2011.19zbMath1292.68079MaRDI QIDQ5494967
Publication date: 30 July 2014
Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ On the Optimal Compression of Sets in PSPACE ⋮ On extracting space-bounded Kolmogorov complexity
This page was built for publication: Randomness Buys Depth for Approximate Counting
