Derandomizing Arthur-Merlin games using hitting sets
From MaRDI portal
Publication:813315
DOI10.1007/s00037-005-0197-7zbMath1085.68058OpenAlexW2098324348MaRDI QIDQ813315
Peter Bro Miltersen, N. V. Vinodchandran
Publication date: 8 February 2006
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-005-0197-7
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (25)
In search of an easy witness: Exponential time vs. probabilistic polynomial time. ⋮ The Untold Story of $$\mathsf {SBP}$$ ⋮ Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Reconstructive dispersers and hitting set generators ⋮ Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ (Nondeterministic) hardness vs. non-malleability ⋮ Statistically sender-private OT from LPN and derandomization ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Local List Recovery of High-Rate Tensor Codes and Applications ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ Arthur and Merlin as oracles ⋮ Lower bounds for non-black-box zero knowledge ⋮ On zero error algorithms having oracle access to one query ⋮ Arthur and Merlin as Oracles ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ The communication complexity of private simultaneous messages, revisited ⋮ Verifiable random functions from non-interactive witness-indistinguishable proofs ⋮ Pseudo-random generators for all hardnesses ⋮ Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More) ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Quantum commitments from complexity assumptions ⋮ The complexity of estimating min-entropy
This page was built for publication: Derandomizing Arthur-Merlin games using hitting sets
