Pseudorandomness for approximate counting and sampling
From MaRDI portal
Publication:2460030
DOI10.1007/s00037-007-0218-9zbMath1125.68058OpenAlexW2168597683MaRDI QIDQ2460030
Ronen Shaltiel, Christopher Umans
Publication date: 14 November 2007
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-007-0218-9
Related Items
Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ (Nondeterministic) hardness vs. non-malleability ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ Arthur and Merlin as oracles ⋮ Relations between average-case and worst-case complexity ⋮ Sparse selfreducible sets and nonuniform lower bounds ⋮ Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games ⋮ On zero error algorithms having oracle access to one query ⋮ Arthur and Merlin as Oracles ⋮ On the de-randomization of space-bounded approximate counting problems ⋮ The complexity of estimating min-entropy
