Uniform generation of NP-witnesses using an NP-oracle
From MaRDI portal
Publication:1854397
DOI10.1006/inco.2000.2885zbMath1006.68050OpenAlexW2094975553MaRDI QIDQ1854397
Mihir Bellare, Erez Petrank, Oded Goldreich
Publication date: 14 January 2003
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/1fc04f4dcb80557c17f003ae4297f7d44f4cd224
Related Items
On the complexity of interactive proofs with bounded communication, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, Circuit lower bounds from learning-theoretic approaches, \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\), Approximate counting in SMT and value estimation for probabilistic programs, (Nondeterministic) hardness vs. non-malleability, On the impossibility of key agreements from quantum random oracles, How to get more mileage from randomness extractors, On Pseudodeterministic Approximation Algorithms., On the (im-)possibility of extending coin toss, Lower bounds for non-black-box zero knowledge, Advanced SMT techniques for weighted model integration
Cites Work
- Unnamed Item
- Unnamed Item
- On the complexity of interactive proofs with bounded communication
- Non-deterministic exponential time has two-prover interactive protocols
- Statistical zero-knowledge languages can be recognized in two rounds
- Random generation of combinatorial structures from a uniform distribution
- NP is as easy as detecting unique solutions
- The probabilistic method yields deterministic parallel algorithms
- Computational complexity and knowledge complexity (extended abstract)
- The Knowledge Complexity of Interactive Proof Systems
- Simulating (log c n )-wise independence in NC
