IP = PSPACE using error-correcting codes

DOI10.1137/110829660MaRDI QIDQ2839183zbMATH OpenOpenAlexFDO

Authors 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

arithmetizationerror-correcting codesinteractive proofsIP = 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)

Recommendations

• IP = SPACE
• scientific article; zbMATH DE number 512981
• IP = PSPACE
• Interactive Coding for Interactive Proofs
• scientific article; zbMATH DE number 4768

Cited in

(15)

• Sumcheck arguments and their applications
• Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier
• Combinatorial PCPs with short proofs
• Codes and Combinatorial Structures from Circular Planar Nearrings
• A hierarchy theorem for interactive proofs of proximity
• Constant-round interactive proofs for delegating computation
• Spatial Isolation Implies Zero Knowledge Even in a Quantum World
• SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption
• Doubly efficient interactive proofs over infinite and non-commutative rings
• Zero-knowledge IOPs approaching witness length
• Blaze: fast SNARKs from interleaved RAA codes
• Proving as fast as computing: succinct arguments with constant prover overhead
• Local proofs approaching the witness length
• Linear prover IOPs in log star rounds
• Sum-check protocol for approximate computations

This page was built for publication: IP = PSPACE using error-correcting codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2839183)