Algebraic Methods for Interactive Proof Systems

An algebraic technique for the construction of interactive proof systems is proposed. The technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. For the proof, a method is developed for reducing the problem of verifying the value of a low-degree polynomial at two points to verifying the value at one new point. The results have implications for program checking, verification, and self-correction. >

Authors

• Carsten Lund
• Lance Fortnow
• Howard J. Karloff
• Noam Nisan

Keywords

• Polynomials
• Context
• Interactive System
• Proof System
• Interactive Proof Systems
• Set Of Languages
• L Matrix
• Proof Of Theorem
• Correction Algorithm
• Polynomial Of Degree
• Number Of Assignments
• Multilinear
• Crucial Fact