IP = PSPACE

By Adi Shamir. 1992

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

A threshold of ln n for approximating set cover (preliminary version) (1996, background): “The notion of PCPs grew out of the theory of interactive proofs (parts of which we will review shortly) and from major breakthroughs in understanding their power [Lund et al. 1992; Shamir 1992; Babai et al. 1991].”
Verifying computations with state (2013, background): “These protocols are based on deep theoretical tools: probabilistically checkable proofs (PCPs) [6, 7], interactive proofs [9, 37, 38, 48, 69], and cryptography [15, 19, 31, 32, 42, 45].”
Verifiable ASICs (2016, methodology): “Using an observation of Thaler [107] and additional simplifications and optimizations, this protocol—which we are not claiming as a contribution of this paper—optimizes Allspice’s CMT-slim protocol [112, §3], which refines CMT [55, §3; 108], which refines GKR [63, §3]; these are all interactive proo”
Foundations of Cryptography: Volume 1, Basic Tools (2001, unknown): “The amazing theorem-proving power of interactive proofs was subsequently demonstrated in [157, 198], showing interactive proofs for coNP and (more generally) for PSPACE , respectively.”
Verifying Computations with Streaming Interactive Proofs (2011, result): “In the most general case where there are no restrictions on the interaction, beyond that the verification (hence also communication) is done in polynomial time, the resulting class IP, can be shown to be equivalent to PSPACE [22].”
How to Delegate and Verify in Public: Verifiable Computation from Attribute-based Encryption (2012, background): “These include interactive proofs [10,14,21,25] and interactive arguments [ 6,18,22].”
Full Accounting for Verifiable Outsourcing (2017, background): “Giraffe’s back-end builds on a line of interactive proofs [12, 49, 50, 58, 76]: GKR [49], as refined and implemented by CMT [36], Allspice [81], Thaler [77], and Zebra [82].”
On the Power of Multi-Prover Interactive Protocols (1994, methodology): “Using the techniques of Lund, Fortnow, Karloo and Nisan, Shamir 29] has shown that every language computable in polynomial space has an interactive proof system.”
From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again (2012, background): “IP = PSPACE.”
Interactive Oracle Proofs (2016, background): “Shamir [Sha92], building on the “sum-check” interactive proof of Lund, Fortnow, Karloff, and Nisan [LFKN92], proved that interactive proofs correspond to languages decidable in polynomial space: IP [poly( n )] = PSPACE .”