Low-End Uniform Hardness versus Randomness Tradeoffs for AM

DOI10.1137/070698348MaRDI QIDQ3575157zbMATH OpenOpenAlexFDO

Authors Ronen Shaltiel, Christopher Umans

Publication date 7 July 2010

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://resolver.caltech.edu/CaltechAUTHORS:20091023-111539349

zbMATH Keywords

Arthur-Merlin gamesderandomizationhardness versus randomnesshitting-set generator

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Round Complexity of Common Randomness Generation: The Amortized Setting
• Robust randomness amplifiers: upper and lower bounds
• Limitations of Hardness vs. Randomness under Uniform Reductions
• Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
• Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
• Computational randomness and lowness
• scientific article; zbMATH DE number 7561765
• Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
• Characterizing lowness for Demuth randomness
• Amortizing randomness complexity in private circuits

Cited in

(13)

• A PCP characterization of AM
• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
• In a world of \(\mathrm{P}=\mathrm{BPP}\)
• Fine-grained derandomization: from problem-centric to resource-centric complexity
• Round complexity versus randomness complexity in interactive proofs
• (Nondeterministic) hardness vs. non-malleability
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Constructive separations and their consequences
• Non-malleable codes with optimal rate for poly-size circuits
• Uniform black-box separations via non-malleable extractors
• Communication complexity vs randomness complexity in interactive proofs
• Instance-wise hardness and refutation versus derandomization for Arthur-Merlin protocols
• Leakage resilience, targeted pseudorandom generators, and mild derandomization of Arthur-Merlin protocols

This page was built for publication: Low-End Uniform Hardness versus Randomness Tradeoffs for AM

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