October 1992 | CARSTEN LUND, LANCE FORTNOW, AND HOWARD KARLOFF AND NOAM NISAN
The paper presents a new algebraic technique for constructing interactive proof systems, which is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a crucial role in recent proofs that IP = PSPACE and MIP = NEXP. The authors demonstrate this by constructing an interactive proof system for the language of 0-1 matrices with a given permanent, leveraging the fact that computing the permanent of 0-1 matrices is \#P-complete. The proof involves a detailed protocol that reduces the problem of verifying the value of a low-degree polynomial at two given points to verifying the value at one new point. The results have implications for program checking, verification, and self-correction, and they do not relativize, as shown by Fortnow and Sipser. The paper also discusses extensions and further research directions, including the possibility of bounded-round interactive proof systems and the study of why the result does not relativize.The paper presents a new algebraic technique for constructing interactive proof systems, which is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a crucial role in recent proofs that IP = PSPACE and MIP = NEXP. The authors demonstrate this by constructing an interactive proof system for the language of 0-1 matrices with a given permanent, leveraging the fact that computing the permanent of 0-1 matrices is \#P-complete. The proof involves a detailed protocol that reduces the problem of verifying the value of a low-degree polynomial at two given points to verifying the value at one new point. The results have implications for program checking, verification, and self-correction, and they do not relativize, as shown by Fortnow and Sipser. The paper also discusses extensions and further research directions, including the possibility of bounded-round interactive proof systems and the study of why the result does not relativize.