2013 · 52 citations · 17 references
ComputingComputer ScienceMathematicsAlgorithmsDelegationTheory Of ComputationCommunication ComplexityComputability TheoryComputational ComplexityInteractive Proof SystemsProof ComplexitySecure Multi-party ComputationComputational Complexity Of LanguagesDelegated ComputationSpace Complexity Of Proofs
We construct a 1-round delegation scheme for every language computable in time t=t(n) and space s=s(n), where the running time of the prover is poly(t) and the running time of the verifier is ~O(n + poly(s)) (where ~O hides polylog(t) factors).
17
Quantum nonlocality as an axiom
Sandu Popescu, Daniel Rohrlich · Foundations of Physics · 1994 · 1.6K citations
Nonlocal correlations as an information-theoretic resource
Jonathan Barrett, Noah Linden, Serge Massar et al. · Physical Review A · 2005 · 633 citations · Full text
A note on efficient zero-knowledge proofs and arguments (extended abstract)
Joe Kilian · 1992 · 586 citations · Full text
Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum · 2008 · 477 citations