IP = PSPACE Using Error-Correcting Codes

DOI10.1137/110829660zbMath1298.68095OpenAlexW1976493784MaRDI QIDQ2839183

Or Meir

Publication date: 4 July 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ae74cd1558d2b636ce931d6437cba6e3da9de29e

zbMATH Keywords

interactive proofserror-correcting codesarithmetizationIP = PSPACEIP theorem

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Theory of error-correcting codes and error-detecting codes (94B99)

Related Items (9)

Sumcheck arguments and their applications ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Spatial Isolation Implies Zero Knowledge Even in a Quantum World ⋮ Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier ⋮ SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ Doubly efficient interactive proofs over infinite and non-commutative rings ⋮ Codes and Combinatorial Structures from Circular Planar Nearrings ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ Combinatorial PCPs with short proofs

This page was built for publication: IP = PSPACE Using Error-Correcting Codes