ECCC-Report TR10-137https://eccc.weizmann.ac.il/report/2010/137Comments and Revisions published for TR10-137en-usSun, 31 Oct 2010 14:17:20 +0200
Revision 5
| IP = PSPACE using Error Correcting Codes |
Or Meir
https://eccc.weizmann.ac.il/report/2010/137#revision5The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), 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. We believe that this establishes a rigorous basis for the aforementioned intuition, and sheds further light on the IP theorem.Sun, 31 Oct 2010 14:17:20 +0200https://eccc.weizmann.ac.il/report/2010/137#revision5
Revision 4
| IP = PSPACE using Error Correcting Codes |
Or Meir
https://eccc.weizmann.ac.il/report/2010/137#revision4The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), 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. We believe that this establishes a rigorous basis for the aforementioned intuition, and sheds further light on the IP theorem.Sun, 24 Oct 2010 18:19:03 +0200https://eccc.weizmann.ac.il/report/2010/137#revision4
Revision 3
| IP = PSPACE using Error Correcting Codes |
Or Meir
https://eccc.weizmann.ac.il/report/2010/137#revision3The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), 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. We believe that this establishes a rigorous basis for the aforementioned intuition, and sheds further light on the IP theorem.Thu, 07 Oct 2010 16:10:50 +0200https://eccc.weizmann.ac.il/report/2010/137#revision3
Revision 2
| IP = PSPACE using Error Correcting Codes |
Or Meir
https://eccc.weizmann.ac.il/report/2010/137#revision2The IP theorem, which asserts that $\bf{IP} = \bf{PSPACE}$ (Lund et. al., and Shamir, in J. ACM 39(4)), 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. We believe that this establishes a rigorous basis for the aforementioned intuition, and sheds further light on the IP theorem.Mon, 04 Oct 2010 15:37:09 +0200https://eccc.weizmann.ac.il/report/2010/137#revision2
Revision 1
| IP = PSPACE using Error Correcting Codes |
Or Meir
https://eccc.weizmann.ac.il/report/2010/137#revision1The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), 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. We believe that this establishes a rigorous basis for the aforementioned intuition, and sheds further light on the IP theorem.Mon, 04 Oct 2010 15:36:29 +0200https://eccc.weizmann.ac.il/report/2010/137#revision1
Paper TR10-137
| IP = PSPACE using Error Correcting Codes |
Or Meir
https://eccc.weizmann.ac.il/report/2010/137The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), 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. We believe that this establishes a rigorous basis for the aforementioned intuition, and sheds further light on the IP theorem.Sun, 29 Aug 2010 15:00:35 +0300https://eccc.weizmann.ac.il/report/2010/137