When Arthur has neither random coins nor time to spare: superfast derandomization of proof systems

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Derandomizing Arthur-Merlin games using hitting sets
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
Expanders, randomness, or time versus space
Minimum disclosure proofs of knowledge
Hardness vs randomness
Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
In search of an easy witness: Exponential time vs. probabilistic polynomial time.
Non-interactive batch arguments for NP from standard assumptions
On the (In)security of Kilian-based SNARGs
Noninteractive zero knowledge for NP from (Plain) Learning With Errors
Pseudorandomness for approximate counting and sampling
Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
Improving Exhaustive Search Implies Superpolynomial Lower Bounds
Random-Self-Reducibility of Complete Sets
Delegating Computation
Interactive Oracle Proofs
Simple extractors for all min-entropies and a new pseudorandom generator
How To Prove Yourself: Practical Solutions to Identification and Signature Problems
IP = PSPACE
Computationally Sound Proofs
On Doubly-Efficient Interactive Proof Systems
Constant-Round Interactive Proofs for Delegating Computation
Quantified Derandomization: How to Find Water in the Ocean
Fiat-Shamir: from practice to theory
On derandomizing algorithms that err extremely rarely
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
Natural proofs
Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
Fiat–Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge)

This page was built for publication: When Arthur has neither random coins nor time to spare: superfast derandomization of proof systems