Communication Complexity of Statistical Distance
Randomized Communication vs. Partition Number
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.