Randomness in interactive proofs
From MaRDI portal
Publication:1321030
DOI10.1007/BF01275487zbMath0802.68053OpenAlexW2118541957MaRDI QIDQ1321030
Shafi Goldwasser, Mihir Bellare, Oded Goldreich
Publication date: 8 May 1994
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01275487
pairwise independenceinteractive proof systemsrandomnessexpander graphssampling methodsArthur-Merlin games
2-person games (91A05) Cryptography (94A60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
A PCP theorem for interactive proofs and applications, Randomness-efficient non-interactive zero knowledge, Derandomized parallel repetition theorems for free games, Unnamed Item, Simple Optimal Hitting Sets for Small-Success RL, Unnamed Item, A PCP Characterization of AM, Bounds on tradeoffs between randomness and communication complexity, Interactive Coding for Interactive Proofs, A Sample of Samplers: A Computational Perspective on Sampling, Another Motivation for Reducing the Randomness Complexity of Algorithms, On the limits of nonapproximability of lattice problems, Derandomized graph products, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
Cites Work
- Unnamed Item
- Lower bounds for sampling algorithms for estimating the average
- On the power of interaction
- On using deterministic functions to reduce randomness in probabilistic algorithms
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Does co-NP have short interactive proofs ?
- Eigenvalues and expanders
- On the power of two-point based sampling
- Explicit constructions of linear-sized superconcentrators
- The longest path in a random graph
- Pseudorandom generators for space-bounded computation
- Universal classes of hash functions
- The random oracle hypothesis is false
- Proving properties of interactive proofs by a generalized counting technique
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- Hecke operators and distributing points on the sphere I
- The Knowledge Complexity of Interactive Proof Systems
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Algebraic methods for interactive proof systems
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- On the hardness of approximating minimization problems
- The complexity of theorem-proving procedures
