IP = PSPACE USING ERROR-CORRECTING CODES

The IP Theorem, which asserts that IP = PSPACE [Lund et al., J. ACM, 39 (1992), pp. 859-868; Shamir, J. ACM, 39 (1992), pp. 878-880], is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a quantified Boolean formula into a related polynomial. The intuition that underlies the use of polynomials is commonly explained by the fact that polynomials constitute good error-correcting codes. However, the known proofs seem tailored to the use of polynomials and do not generalize to arbitrary error-correcting codes. In this work, we show that the IP theorem can be proved by using general error-correcting codes and their tensor products. We believe that this establishes a rigorous basis for the aforementioned intuition and sheds further light on the IP theorem.