Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #7 to TR10-137 | 6th April 2022 13:54

IP = PSPACE using Error Correcting Codes

RSS-Feed




Revision #7
Authors: Or Meir
Accepted on: 6th April 2022 13:54
Downloads: 89
Keywords: 


Abstract:

The 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.



Changes to previous version:

Fixed typos in the proof of Proposition 3.10 and in the statement of Theorem 4.4.


Revision #6 to TR10-137 | 6th April 2022 10:59

IP = PSPACE using Error Correcting Codes





Revision #6
Authors: Or Meir
Accepted on: 6th April 2022 10:59
Downloads: 44
Keywords: 


Abstract:

The 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.



Changes to previous version:

Changed the construction of the multiplication codes in order to guarantee that they are systematic.


Revision #5 to TR10-137 | 31st October 2010 14:17

IP = PSPACE using Error Correcting Codes





Revision #5
Authors: Or Meir
Accepted on: 31st October 2010 14:17
Downloads: 2775
Keywords: 


Abstract:

The 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.


Revision #4 to TR10-137 | 24th October 2010 18:19

IP = PSPACE using Error Correcting Codes





Revision #4
Authors: Or Meir
Accepted on: 24th October 2010 18:19
Downloads: 2453
Keywords: 


Abstract:

The 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.


Revision #3 to TR10-137 | 7th October 2010 16:10

IP = PSPACE using Error Correcting Codes





Revision #3
Authors: Or Meir
Accepted on: 7th October 2010 16:10
Downloads: 2466
Keywords: 


Abstract:

The 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.


Revision #2 to TR10-137 | 4th October 2010 15:37

IP = PSPACE using Error Correcting Codes





Revision #2
Authors: Or Meir
Accepted on: 4th October 2010 15:37
Downloads: 2318
Keywords: 


Abstract:

The 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.


Revision #1 to TR10-137 | 4th October 2010 15:36

IP = PSPACE using Error Correcting Codes





Revision #1
Authors: Or Meir
Accepted on: 4th October 2010 15:36
Downloads: 2922
Keywords: 


Abstract:

The 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.


Paper:

TR10-137 | 29th August 2010 14:56

IP = PSPACE using Error Correcting Codes





TR10-137
Authors: Or Meir
Publication: 29th August 2010 15:00
Downloads: 3291
Keywords: 


Abstract:

The 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.



ISSN 1433-8092 | Imprint