Pseudorandomness for approximate counting and sampling

DOI10.1007/S00037-007-0218-9MaRDI QIDQ2460030zbMATH OpenOpenAlexFDO

Authors Ronen Shaltiel, Christopher Umans

Publication date 14 November 2007

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s00037-007-0218-9

zbMATH Keywords

approximate countingArthur Merlin gamesDerandomizationnondeterministic circuitspseudorandomness

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
• Hardness vs randomness
• Derandomizing Arthur-Merlin games under uniform assumptions
• Derandomizing Arthur-Merlin games using hitting sets
• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games

Cited in

(25)

• Sparse selfreducible sets and nonuniform lower bounds
• Uniform generation of NP-witnesses using an NP-oracle
• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
• On the de-randomization of space-bounded approximate counting problems
• On zero error algorithms having oracle access to one query
• The complexity of estimating min-entropy
• On the randomness complexity of efficient sampling
• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
• Arthur and Merlin as Oracles
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Pseudo-derandomizing learning and approximation
• (Nondeterministic) hardness vs. non-malleability
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
• Arthur and Merlin as oracles
• When Arthur has neither random coins nor time to spare: superfast derandomization of proof systems
• Nearly optimal pseudorandomness from hardness
• Non-malleable codes with optimal rate for poly-size circuits
• Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity
• Uniform black-box separations via non-malleable extractors
• Communication complexity vs randomness complexity in interactive proofs
• Leakage resilience, targeted pseudorandom generators, and mild derandomization of Arthur-Merlin protocols
• Bounded simultaneous messages
• Regularization of low error PCPs and an application to MCSP
• Relations between average-case and worst-case complexity

This page was built for publication: Pseudorandomness for approximate counting and sampling

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