Algebraic methods for interactive proof systems

1992/10/01 by Carsten Lund, Lance Fortnow, Howard Karloff +1 · 12 citations
Computer Science · #Logic, programming, and type systems #Formal Methods in Verification #Complexity and Algorithms in Graphs

paper · pdf · doi:10.1145/146585.146605

openalex publication_date 1992/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A new algebraic technique for the construction of interactive proof systems is presented. Our technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a pivotal role in the recent proofs that IP = PSPACE [28] and that MIP = NEXP [4].

Cited by

• Software Engineering and complexity in effective Algebraic Geometry
• Notes on Univariate Sumcheck
• Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
• New Verification Schemes for Frequency-Based Functions on Data Streams
• Scalable Zero Knowledge with No Trusted Setup
• Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies
• BPP has subexponential time simulations unlessEXPTIME has publishable proofs
• Algebrization
• Computational Complexity
• Quantum Computing since Democritus
• The Nature of Computation
• Carsten Lund [wikipedia]