Randomness in interactive proofs
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3980487 (Why is no real title available?)
- Algebraic methods for interactive proof systems
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Does co-NP have short interactive proofs ?
- Eigenvalues and expanders
- Explicit constructions of linear-sized superconcentrators
- Hecke operators and distributing points on the sphere I
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Lower bounds for sampling algorithms for estimating the average
- New Algorithms for Finding Irreducible Polynomials Over Finite Fields
- On the hardness of approximating minimization problems
- On the power of interaction
- On the power of two-point based sampling
- On using deterministic functions to reduce randomness in probabilistic algorithms
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- Proving properties of interactive proofs by a generalized counting technique
- Pseudorandom generators for space-bounded computation
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- The Knowledge Complexity of Interactive Proof Systems
- The complexity of theorem-proving procedures
- The longest path in a random graph
- The random oracle hypothesis is false
- Universal classes of hash functions
Cited in
(20)- Bounds on tradeoffs between randomness and communication complexity
- scientific article; zbMATH DE number 7563815 (Why is no real title available?)
- Interactive Coding for Interactive Proofs
- Randomness-efficient non-interactive zero knowledge
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Forward induction and public randomization
- Simple optimal hitting sets for small-success RL
- A PCP characterization of AM
- Derandomized graph products
- On the limits of nonapproximability of lattice problems
- A sample of samplers: a computational perspective on sampling
- Proving properties of interactive proofs by a generalized counting technique
- A PCP theorem for interactive proofs and applications
- Hardness self-amplification: simplified, optimized, and unified
- Derandomized parallel repetition theorems for free games
- Round complexity versus randomness complexity in interactive proofs
- scientific article; zbMATH DE number 7650126 (Why is no real title available?)
- Another motivation for reducing the randomness complexity of algorithms
- Randomized proofs in arithmetic
- A protocol for generating random elements with their probabilities
This page was built for publication: Randomness in interactive proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1321030)
