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 #3 to TR16-040 | 6th September 2017 03:49

Affine Relativization: Unifying the Algebrization and Relativization Barriers

RSS-Feed




Revision #3
Authors: Baris Aydinlioglu, Eric Bach
Accepted on: 6th September 2017 03:49
Downloads: 1399
Keywords: 


Abstract:

We strengthen existing evidence for the so-called "algebrization barrier". Algebrization --- short for algebraic relativization --- was introduced by Aaronson and Wigderson (AW) (STOC 2008) in order to characterize proofs involving arithmetization, simulation, and other "current techniques". However, unlike relativization, eligible statements under this notion do not seem to have basic closure properties, making it conceivable to take two proofs, both with algebrizing conclusions, and combine them to get a proof without. Further, the notion is undefined for most types of statements, and does not seem to yield a general criterion by which we can tell, given a proof, whether it algebrizes. In fact the very notion of an algebrizing proof is never made explicit, and casual attempts to define it are problematic. All these issues raise the question of what evidence, if any, is obtained by knowing whether some statement does or does not algebrize.

We give a reformulation of algebrization without these shortcomings. First, we define what it means for any statement / proof to hold relative to any language, with no need to refer to devices like a Turing machine with an oracle tape. Our approach dispels the widespread misconception that the notion of oracle access is inherently tied to a computational model. We also connect relativizing statements to proofs, by showing that every proof that some statement relativizes is essentially a relativizing proof of that statement.

We then define a statement / proof as relativizing *affinely* if it holds relative to every *affine oracle* --- here an affine oracle is the result of a particular error correcting code applied to the characteristic string of a language. We show that every statement that AW declare as algebrizing does relativize affinely, in fact has a *proof* that relativizes affinely, and that no such proof exists for any of the statements shown not-algebrizing by AW in the classical computation model.

Our work complements, and goes beyond, the subsequent work by Impagliazzo, Kabanets, and Kolokolova (STOC 2009), which also proposes a reformulation of algebrization, but falls short of recovering some key results of AW, most notably regarding the NEXP versus P/poly question.

Using our definitions we obtain new streamlined proofs of several classic results in complexity, including PSPACE $\subset$ IP and NEXP $\subset$ MIP. This may be of separate interest.



Changes to previous version:

Revised journal version.


Revision #2 to TR16-040 | 6th September 2017 03:46

Affine Relativization: Unifying the Algebrization and Relativization Barriers





Revision #2
Authors: Baris Aydinlioglu, Eric Bach
Accepted on: 6th September 2017 03:46
Downloads: 940
Keywords: 


Abstract:

We strengthen existing evidence for the so-called "algebrization barrier". Algebrization --- short for algebraic relativization --- was introduced by Aaronson and Wigderson (AW) in order to characterize proofs involving arithmetization, simulation, and other "current techniques". However, unlike relativization, eligible statements under this notion do not seem to have basic closure properties, making it conceivable to take two proofs, both with algebrizing conclusions, and combine them to get a proof without. Further, the notion is undefined for most types of statements, and does not seem to yield a general criterion by which we can tell, given a proof, whether it algebrizes. In fact the very notion of an algebrizing proof is never made explicit, and casual attempts to define it are problematic. All these issues raise the question of what evidence, if any, is obtained by knowing whether some statement does or does not algebrize.

We reformulate algebrization to handle these shortcomings. We first define a statement as *relativizing* if, intuitively, it is insensitive to the choice of a Boolean basis, and then as *relativizing affinely* if, roughly, it relativizes with respect to every affine extension --- here an affine extension is the result of a particular error correcting code applied to the characteristic string of a language. We also define the notion of a *proof* to relativize (affinely), while ensuring closure under inference. We show that all statements that AW declare as algebrizing can be derived via an affinely relativizing proof, and that no such proof exists for any of the statements shown not-algebrizing by AW in the classical computation model.

Our work complements, and goes beyond, the subsequent work by Impagliazzo, Kabanets, and Kolokolova (IKK), which also proposes a reformulation of algebrization, but falls short of recovering some key results of AW, most notably regarding the NEXP versus P/poly question.

One consequence of our definitions is a demystified perspective on the extent to which relativizing techniques view computation as a "black box" and current uses of arithmetization do not. As a bonus, we give new streamlined proofs of PSPACE $\subset$ IP and NEXP $\subset$ MIP.


Revision #1 to TR16-040 | 16th June 2016 03:16

Affine Relativization: Unifying the Algebrization and Relativization Barriers





Revision #1
Authors: Baris Aydinlioglu, Eric Bach
Accepted on: 16th June 2016 03:16
Downloads: 1551
Keywords: 


Abstract:

We strengthen existing evidence for the so-called "algebrization barrier". Algebrization --- short for algebraic relativization --- was introduced by Aaronson and Wigderson (AW) (STOC 2008) in order to characterize proofs involving arithmetization, simulation, and other "current techniques". However, unlike relativization, eligible statements under this notion do not seem to have basic closure properties, making it conceivable to take two proofs, both with algebrizing conclusions, and combine them to get a proof without. Further, the notion is undefined for most types of statements, and does not seem to yield a general criterion by which we can tell, given a proof, whether it algebrizes. In fact the very notion of an algebrizing proof is never made explicit, and casual attempts to define it are problematic. All these issues raise the question of what evidence, if any, is obtained by knowing whether some statement does or does not algebrize.

We reformulate algebrization to handle these shortcomings. We first define a statement as *relativizing* if, intuitively, it is insensitive to the choice of a Boolean basis, and then as *relativizing affinely* if, roughly, it relativizes with respect to every affine extension --- here an affine extension is the result of a particular error correcting code applied to the characteristic string of a language. We also define the notion of a *proof* to relativize (affinely), while ensuring closure under inference. We show that all statements that AW declare as algebrizing can be derived via an affinely relativizing proof, and that no such proof exists for any of the statements shown not-algebrizing by AW in the classical computation model.

Our work complements, and goes beyond, the subsequent work by Impagliazzo, Kabanets, and Kolokolova (STOC 2009), which also proposes a reformulation of algebrization, but falls short of recovering some key results of AW, most notably regarding the NEXP versus P/poly question.

One consequence of our definitions is a demystified perspective on the extent to which relativizing techniques view computation as a "black box" and current uses of arithmetization do not. As another consequence, we give new streamlined proofs of several classic results in complexity, including PSPACE $\subset$ IP and NEXP $\subset$ MIP.



Changes to previous version:

Full version.


Paper:

TR16-040 | 16th March 2016 18:48

Affine Relativization: Unifying the Algebrization and Relativization Barriers





TR16-040
Authors: Baris Aydinlioglu, Eric Bach
Publication: 17th March 2016 12:18
Downloads: 2028
Keywords: 


Abstract:

We strengthen existing evidence for the so-called "algebrization barrier". Algebrization --- short for algebraic relativization --- was introduced by Aaronson and Wigderson (AW) in order to characterize proofs involving arithmetization, simulation, and other "current techniques". However, unlike relativization, eligible statements under this notion do not seem to have basic closure properties, making it conceivable to take two proofs, both with algebrizing conclusions, and combine them to get a proof without. Further, the notion is undefined for most types of statements, and does not seem to yield a general criterion by which we can tell, given a proof, whether it algebrizes. In fact the very notion of an algebrizing proof is never made explicit, and casual attempts to define it are problematic. All these issues raise the question of what evidence, if any, is obtained by knowing whether some statement does or does not algebrize.

We reformulate algebrization to handle these shortcomings. We first define a statement as *relativizing* if, intuitively, it is insensitive to the choice of a Boolean basis, and then as *relativizing affinely* if, roughly, it relativizes with respect to every affine extension --- here an affine extension is the result of a particular error correcting code applied to the characteristic string of a language. We also define the notion of a *proof* to relativize (affinely), while ensuring closure under inference. We show that all statements that AW declare as algebrizing can be derived via an affinely relativizing proof, and that no such proof exists for any of the statements shown not-algebrizing by AW in the classical computation model.

Our work complements, and goes beyond, the subsequent work by Impagliazzo, Kabanets, and Kolokolova (IKK), which also proposes a reformulation of algebrization, but falls short of recovering some key results of AW, most notably regarding the NEXP versus P/poly question.

One consequence of our definitions is a demystified perspective on the extent to which relativizing techniques view computation as a "black box" and current uses of arithmetization do not. As a bonus, we give new streamlined proofs of PSPACE $\subset$ IP and NEXP $\subset$ MIP.



ISSN 1433-8092 | Imprint