CS代考计算机代写 scheme algorithm decision tree Algebrization: A New Barrier in Complexity Theory

Proof. Our proof closely follows the proof of Bennett and Gill [6] that PA ̸= NPA with probability 1 over A.
Similarly to Lemma 4.10, given a Boolean point w and a finite field F, let Dn,w,F be the uniform
distribution over all multiquadratic polynomials p􏰲: Fn → F such that p(w) = 1 and p(z) = 0 for
all Boolean z ̸= w. Then we generate the oracle A according to following distribution. For each
n∈N,firstdraww ∈{0,1}n uniformlyatrandom,andsetA (w )=1andA􏰲(z)=0forall nnnn
n-bit Boolean strings z ̸= wn. Next, for every finite field F, draw the extension An,F of An from
Dn,wn,F.
WedefinethelanguageLasfollows: 0i1n−i ∈Lifandonlyiftheith bitofwn isa1,andx∈/L
in−i􏰲 A A􏰲 forallxnotoftheform01 . ClearlyL∈NP . OurgoalistoshowthatL∈/BPP with
probability 1 over the choice of A.
Fix a BPP oracle machine M. Then let EM,n,i be the event that M correctly decides whether
0i1n−i ∈ L, with probability at least 2/3 over M’s internal randomness, and let EM,n := EM,n,1 ∧ · · · ∧ EM,n,n.
Supposing EM,n holds, with high probability we can recover wn in polynomial time, by simply running M several times on each input 0i1n−i and then outputting the majority answer as the ith bit of wn. But Lemma 4.10 implies that after making t queries, we can guess wn with probability at most
t+1,
2n 2n − t 􏰲
just as if we had oracle access only to An and not to the extensions An,F.
So given n, choose another input size n′ ≫ n which is so large that on inputs of size n or less,
M cannot have queried A􏰲n′,F for any F (for example, n′ = 22n will work for sufficiently large n). Then for all sufficiently large n, we must have
Pr􏰥EM,n′ |EM,1∧···∧EM,n􏰦≤1. A􏰲 3
This implies that
But since there is only a countable infinity of BPP machines, by the union bound we get
P􏰲r [ E M , 1 ∧ E M , 2 ∧ · · · ] = 0 . A
P􏰲r [ ∃ M : E M , 1 ∧ E M , 2 ∧ · · · ] = 0 A
which is what we wanted to show.
Theorem 5.4 readily extends to show any proof of NP ⊂ P/poly would require non-algebrizing
techniques:
Theorem 5.5 There exist A, A􏰲 such that NPA ̸⊂ PA􏰲/poly.
Proof Sketch. Suppose we have a PA􏰲/poly machine that decides a langu􏰲age L ∈ NPA using an advice string of size nk. Then by guessing the advice string, we get a BPPA machine that decides
L on all inputs with probability Ω(2−nk ). We can then run the BPPA􏰲 machine sequentially on (say) n2k inputs x1 , . . . , xn2k , and decide all of them with a greater probability than is allowed by the proof of Theorem 5.4.10
10Because of the requirement that the BPPA􏰲 machine operates sequentially—i.e., that it outputs the answer for each input xt before seeing the next input xt+1—there is no need here for a direct product theorem. On the other hand, proving direct product theorems for algebraic query complexity is an interesting open problem.
25

5.3 Non-Algebrizing Techniques Needed for Circuit Lower Bounds
We now give an oracle A and extension A􏰲 such that NEXPA􏰲 ⊂ PA/poly. This implies that any proof of NEXP ̸⊂ P/poly will require non-algebrizing techniques.
Theorem 5.6 There exist A, A􏰲 such that NTIMEA􏰲 (2n) ⊂ SIZEA (n).
Proof. Let M1, M2, . . . be an enumeration of NTIME (2n) oracle machines. Then on inputs of size n, it suffices to simulate M1, . . . , Mn, since then every Mi will be simulated on all but finitely many input lengths.
For simplicity, we will assume that on inputs of size n, the Mi’s can query only a single poly- nomial, p : F4n → F. Later we will generalize to the case where the Mi’s can query A􏰲n,F for every n and F simultaneously.
We construct p by an iterative process. We are dealing with n2n pairs of the form ⟨i, x⟩, where x ∈ {0, 1}n is an input and i ∈ [n] is the label of a machine. At every iteration, each ⟨i, x⟩ will be either satisfied or unsatisfied, and each point in F4n will be either active or inactive. Initially all ⟨i, x⟩’s are unsatisfied and all points are active.
To fix an active point y will mean we fix the value of p(y) to some constant cy, and switch y from active to inactive. Once y is inactive, it never again becomes active, and p(y) never again changes.
We say that y is fixed consistently, if after it is fixed there still exists a multiquadratic extension polynomial p : F4n → F such that p (y) = cy for all inactive points y. Then the iterative process consists of repeatedly asking the following question:
Does there exist an unsatisfied ⟨i, x⟩, such that by consistently fixing at most 2n active points, we can force Mi to accept on input x?
If the answer is yes, then we fix those points, switch ⟨i,x⟩ from unsatisfied to satisfied, and repeat. We stop only when we can no longer find another ⟨i, x⟩ to satisfy.
Let D be the set of inactive points when this process halts. Then |D| ≤ n22n. So by Lemma 4.5, there exists a subset G ⊆ {0, 1}4n, with |G| ≥ 24n − n22n, such that for any Boolean function f : {0, 1}4n → {0, 1}, there exists a multiquadratic polynomial p : F4n → F satisfying
(i) p(y)=cy forally∈D,
(ii) p(z)=f(z)forallz∈G,and (iii) p (z) ∈ {0, 1} for all Boolean z.
To every machine-input pair ⟨i, x⟩, associate a unique string wi,x ∈ {0, 1}4n in some arbitrary way. Then for all ⟨i, x⟩ we have
n22n Pr 4n [z⊕wi,x ∈G]≥1− 24n .
z∈{0,1}
So by the union bound, there exists a fixed string z′ ∈ {0, 1}4n such that z′ ⊕ wi,x ∈ G for all ⟨i, x⟩. We will choose the Boolean function f so that for every ⟨i, x⟩ pair, f (z′ ⊕ wi,x) encodes whether or not Mi accepts on input x. Note that doing so cannot cause any additional ⟨i, x⟩ pairs to accept, for if it could, then we would have already forced those pairs to accept during the iterative process.
Our linear-size circuit for simulating the Mi’s will now just hardwire the string z′. 26

Finally, let us generalize to the case where the Mi’s can query A􏰲n,F for any input length n and finite field F of their choice. This requires only a small change to the original proof. We construct A􏰲 in stages. At stage n, assume that A􏰲1,F, . . . , A􏰲n−1,F have already been fixed for every F. Then our goal is to fix A􏰲n,F for every F. Let YF be the set of points in Fn for which the value of A􏰲n,F was fixed in one of the previous n − 1 stages. Then
n−1
􏰕|YF|≤ 􏰕m22m ≤n22n.
F m=1
So by Lemma 4.5, for all F we can find multiquadratic polynomials A􏰲n,F : F4n → F that satisfy all the forcing conditions, and that also encode in some secret location whether Mi accepts on input xforalli∈[n]andx∈{0,1}n. 􏰲 A􏰲
By a standard padding argument, Theorem 5.6 immediately gives A,A such that NEXP ⊂ PA/poly. This collapse is almost the best possible, since Theorem 3.17 implies that there do not
exist A, A􏰲 such that MAA􏰲 ⊂ PA/poly. EXP
Wilson [43] gave an oracle A relative to which EXPNPA ⊂ PA/poly. Using similar ideas, one can straightforwardly generalize the construction of Theorem 5.6 to obtain the following:
Theorem 5.7 There exist A, A􏰲 such that EXPNPA􏰲 ⊂ PA/poly.
One can also combine the ideas of Theorem 5.6 with those of Theorem 5.4 to obtain the following:
Theorem 5.8 There exist A, A􏰲 such that BPEXPA􏰲 ⊂ PA/poly.
We omit the details of the above two constructions. However, we would like to mention one
interesting implication of Theorem 5.8. Fortnow and Klivans [14] recently showed the following:
Theorem 5.9 ([14]) If the class of polynomial-size circuits is exactly learnable by a BPP machine from membership and equivalence queries, or is PAC-learnable by a BPP machine with respect to the uniform distribution, then BPEXP ̸⊂ P/poly.
By combining Theorem 5.9 with Theorem 5.8, we immediately get the following corollary:
􏰲A􏰲
Corollary 5.10 There exist A,A such that P /poly circuits are not exactly learnable from mem-
bership and equivalence queries (nor PAC-learnable with respect to the uniform distribution), even if the learner is a BPP machine with oracle access to A.
Informally, Corollary 5.10 says that learning polynomial-size circuits would necessarily require non-algebrizing techniques.
5.4 Non-Algebrizing Techniques Needed for Other Problems
We can use the communication complexity transfer principle from Section 4.3 to achieve many other separations.
Theorem 5.11 There exist A, A􏰲 such that (i) NPA ̸⊂ BPPA􏰲,
27

(ii) coNPA ̸⊂ MAA􏰲, (iii) PNPA ̸⊂ PPA􏰲,
(iv) NPA ̸⊂ BQPA􏰲,
(v) BQPA ̸⊂ BPPA􏰲, and
(vi) QMAA ̸⊂ MAA􏰲. 􏰲
Furthermore, for all of these separations A is simply the multilinear extension of A.
Proof Sketch. Let us first explain the general idea, before applying it to prove these separations.
Given a complexity class C, let Ccc be the communication complexity analogue of C: that is, the
class of communication predicates f : {0, 1}N × {0, 1}N → {0, 1} that are decidable by a C machine
AA􏰲 􏰲
using O(po􏰲lylogN) communication. Also suppose C ⊆ D for all oracles A and multilinear
extensions A of A. Then the transfer principle (Theorem 4.11) would imply that Ccc ⊆ Dcc. Thus, if we kn􏰲ow already that Ccc ̸⊂ Dcc, we can use that to conclude that there exist A,A such that CA ̸⊂ DA.
We now apply this idea to prove the six separations listed above.
(i) Recall that Kalyasundaram and Schnitger [22] (see also [33]) proved an Ω (N ) lower bound on the randomized communication complexity of the Disjointness predicate. From this, together with a st􏰲andard diagonalization a􏰲rgument, one easily gets that NPcc ̸⊂ BPPcc. Hence there exist A, A such that NPA ̸⊂ BPPA.
(ii) Klauck [25] has generalized the lower bound of [33, 22] to show that Disjointness has MA communicatio􏰲n complexity Ω(√N). From this it follows that coNPcc ̸⊂ MAcc, and hence
coNPA ̸⊂ MAA.
(iii) Buhrman, Vereshchagin, and de Wolf [9] showed that PNP ̸⊂ PP , which implies PNPA ̸⊂ PPA􏰲.
(iv) Razborov [34] showed that Disjointness has quantum communication complexity Ω(√N). This implies that NPcc ̸⊂ BQPcc, and hence NPA ̸⊂ BQPA􏰲.11
(v) Raz [30] gave an exponential separation between randomized and quantum communication complexities for a pr􏰲omise problem. This implies that PromiseBQPcc ̸⊂ PromiseBPPcc, and􏰲 hence BQPA ̸⊂ BPPA (note that we can remove the promise by simply choosing oracles A, A that satisfy it).
(vi) Raz and Shpilka [3􏰲1] showed that PromiseQMAcc ̸⊂ PromiseMAcc. As in (iv), this implies that QMAA ̸⊂ MAA.
We end by mentioning, without details, two other algebraic oracle separations that can be proved using the connection to communication complexity.
11Let us remark that, to our knowledge, this reduction constitutes the first use of quantum communication com- plexity to obtain a new lower bound on quantum query complexity. The general technique might be applicable to other problems in quantum lower bounds.
cc cc
28

First, Andy Drucker (personal communication) has found A,A􏰲 such that NPA ̸⊂ PCPA􏰲, thus giving a sense in which “the PCP Theorem is non-algebrizing.” Here PCP is defined similarly to MA,exceptthattheverifierisonlyallowedtoexamineO(1)bitsofthewitness. Druckerprovesthis result by lower-bounding the “PCP communication complexity” of the Non-Disjointness predicate. In particular, if Alice and Bob are given a PCP of m bits, of which they can examine at most c, then verifying Non-Disjointness requires at least N/mO(c) bits of communication. It remains open what happens when m is large compared to N.
Second, Hartmut Klauck (personal communication) has found A, A􏰲 such that coNPA ̸⊂ QMAA􏰲, by proving an Ω(N1/3) lower bound on the QMA communication complexity of the Disjointness predicate.12
6 The Integers Case
For simplicity, thus far in the paper we restricted ourselves to low-degree extensions over fields (typically, finite fields). We now consider the case of low-degree extensions over the integers. When we do this, one complication is that we can no longer use Gaussian elimination to construct “adversary polynomials” with desired properties. A second complication is that we now need to worry about the size of an extension oracle’s inputs and outputs (i.e., the number of bits needed to specify them). For both of these reasons, proving algebraic oracle separations is sometimes much harder in the integers case than in the finite field case.
Formally, given a vector of integers v = (v1, . . . , vn), we define the size of v,
Definition 6.1 (Extension Oracle Over The Integers) Let Am : {0, 1}m → {0, 1} be a Boolean function. Then an extension of Am over the integers Z is a polynomial A􏰱m : Zm → Z such that
m
⌈log2 (|vi| + 2)⌉ ,
We can now give the counterpart of Definition 2.2 for integer extensions:
􏰕n i=1
size (v) :=
to be a rough measure of the number of bits needed to specify v. Notice that size (v) ≥ n for all v.
􏰱􏰱􏰱
Am (x) = Am (x) whenever x ∈ {0,1} . Also, given an oracle A = (Am), an extension A of A is a collection of polynomials A􏰱m : Zm → Z, one for each m ∈ N, such that
(i) Am is an extension of Am for all m,
(ii) there exists a constant c such that mdeg(A􏰱m) ≤ c for all m, and
(iii) there exists a polynomial p such that size(A􏰱m (x)) ≤ p (m + size (x)) for all x ∈ Zm.
A􏰱 A􏰱[poly] 􏰱
Then given a complexity class C, by C or C we mean the class of languages decidable
by a C machine that, on inputs of length n, can query Am for any m or any m = O(poly(n)) respectively.
12It is an interesting question whether his lower bound is tight. We know that Disjointness admits a quantum protocol with O(√N ) communication [7, 2], as well as an MA-protocol with O(√N log N ) communication (see Sec- tion 7.2). The question is whether these can be combined somehow to get a QMA-protocol with, say, O(N1/3) communication.
29

Notice that integer extensions can always be used to simulate finite field extensions—since given an integer A􏰱m (x), together with a field F of order qk where q is prime, an algorithm can just compute A􏰲m,F (x) := A􏰱m (x) mod q for itself. In other words, for every integer extension A􏰱, there
exists a finite field extension A􏰲 such that DA􏰲 ⊆ DA􏰱 for all complexity classes D capable of modular arithmetic. Hence any result of the form CA ⊆ DA􏰲 for all A, A􏰲 automatically implies CA ⊆ DA􏰱 for all A, A􏰱. Likewise, any construction of oracles A, A􏰱 such that CA ̸⊂ DA􏰱 automatically implies the existence of A, A􏰲 such that CA ̸⊂ DA􏰲.
We now define the model of algebraic query complexity over the integers.
Definition 6.2 (Algebraic Query Complexity Over Z) Let f : {0, 1}N → {0, 1} be a Boolean function,andletsandcbepositiveintegers. Also,letMbethesetofdetermi􏰱nisticalgorithms M such that􏰱 for every oracle A : {0, 1}n → {0, 1}, and every integer extension A : Zn → Z of A with mdeg(A) ≤ c,
(i) MA􏰱 outputs f (A), and
(ii) every query x made by M A􏰱 satisfies size (x) ≤ s.
Then the deterministic algebraic query complexity of f over Z is defined as
D􏰱s,c(f):= min max
M ∈M A,A􏰱:mdeg(A􏰱)≤c
TM(A􏰱),
where TM(A􏰱) is the number of queries to A􏰱􏰱made by MA􏰱. (For the purposes of this definition, we do not impose any upper bound on size(A (x)).) The randomized and quantum algebraic query complexities R􏰱s,c (f) and Q􏰱s,c (f) are defined similarly, except with (bounded-error) randomized and quantum algorithms in place of deterministic ones.
Notice that proving lower bounds on D􏰱s,c, R􏰱s,c, and Q􏰱s,c becomes harder as s increases, and easier as c increases.
Our goal is twofold: (1) to prove lower bounds on the above-defined query complexity measures, and (2) to use those lower bounds to prove algebraic oracle separations over the integers (for example, that there exist A, A􏰱 such that NPA ̸⊂ PA􏰱).
6.1 Lower Bounds by Communication Complexity
A first happy observation is that every lower bound or oracle separation proved using Theorem 4.11 (the communication complexity transfer principle) automatically carries over to the integers case. This is so because of the following direct analogue of Theorem 4.11 for integer extensions:
Theorem 6.3 Let A : {0,1}n → {0,1} be a Boolean function, and let A􏰱 : Zn → Z be the unique multilinear extension of A over Z. Suppose one can evaluate some Boolean predicate f of A using T deterministic adaptive queries to A􏰱, where each query x ∈ Zn satisfies size (x) ≤ s. Also, let A0 and A1 be the subfunctions of A obtained by restricting the first bit to 0 or 1 respectively. Then if Alice is given the truth table of A0 and Bob is given the truth table of A1, they can jointly evaluate f (A) using O (T s) bits of communication.
The proof of Theorem 6.3 is essentially the same as the proof of Theorem 4.11, and is therefore omitted.
By analogy to Theorem 4.12, Theorem 6.3 has the following immediate consequence for the randomized query complexity of Disjointness over the integers:
30

Theorem 6.4 R􏰱s,1 (DISJ) = Ω (2n/s) for all s.
Proof. Suppose R􏰱s,1 (DISJ) = o(2n/s). Then by Theorem 6.3, we get a randomized protocol for Disjointness with communication cost o(2n), thereby violating the lower bound of Razborov [33] and Kalyasundaram and Schnitger [22].
One can also use Theorem 6.3 to construct oracles A and integer extensions A􏰱 such that
• NPA ̸⊂ PA􏰱,
• RPA ̸⊂ PA􏰱,
• NPA ̸⊂ BQPA􏰱,
and so on for all the other oracle separations obtained in Section 5.4 in the finite field case. The proofs are similar to those in Section 5.4 and are therefore omitted.
6.2 Lower Bounds by Direct Construction
Unlike with the communication complexity arguments, when we try to port the direct construction arguments of Section 4.2 to the integers case we encounter serious new difficulties. The basic source of the difficulties is that the integers are not a field but a ring, and thus we can no longer construct multilinear polynomials by simply solving linear equations.
In this section, we partly overcome this problem by using some tools from elementary number theory, such as Chinese remaindering and Hensel lifting. The end result will be an exponential lower bound on D􏰱s,2 (OR): the number of queries to a multiquadratic integer extension A􏰱 : Zn → Z needed to decide whether there exists an x ∈ {0,1}n with A(x) = 1, assuming the queries are deterministic and have size at most s ≪ 2n.
Unfortunately, even after we achieve this result, we will still not be able to use it to prove oracle separations like NPA ̸⊂ PA􏰱. The reason is technical, and has to do with size(A􏰱(x)): the number of bits needed to specify an output of A􏰱. In our adversary construction, size(A􏰱(x)) will grow like O (size(x) + ts), where t is the number of queries made by the algorithm we are fighting against and s is the maximum size of those queries. The dependence on size(x) is fine, but the dependence on t and s is a problem for two reasons. First, the nu􏰱mber of bits needed to store A􏰱’s output might exceed the running time of the algorithm that calls A! Second, we ultimate􏰱ly want to diagonalize against all polynomial-time Turing machines, and this will imply that size(A (x)) must grow faster than polynomial.
Nevertheless, both because we hope it will lead to stronger results, and because the proof is mathematically interesting, we now present a lower bound on D􏰱s,2 (OR).
Our goal is to arrive at a lemma similar to Lemma 4.3 in the field case; its analogue will be Lemma 6.9 below.
Lemma 6.5 Let y1,…,yt be points in Zn and let q be a prime. Then there exists a multilinear polynomial hq : Zn → Z such that
(i) hq (yi) ≡ 0(modq) for all i ∈ [t], and
(ii) hq (z) = 1 for at least 2n − t Boolean points z.
(Note that hq could be non-Boolean on the remaining Boolean points.) 31

Proof. Let N = 2n; then we can label the N Boolean points z1,…,zN. For all i ∈ [N], let δi be the unique multilinear polynomial satisfying δi (zi) = 1 and δi (zj) = 0 for all j ̸= i.
Now let Λ be a (t+N)×N integer matrix whose top t rows are labeled by y1,…,yt, whose bottom N rows are labeled by z1,…,zN, and whose columns are labeled by δ1,…,δN. The (x,δi) entry is equal to δi (x). We assume without loss of generality that the top t × N submatrix of Λ has full rank mod q, for if it does not, then we simply remove rows until it does. Notice that the bottom N × N submatrix of Λ is just the identity matrix I.
Now remove t of the bottom N rows, in such a way that the resulting N × N submatrix B of Λ is nonsingular mod q. Then for every vector v ∈ FNq , the system Bα ≡ v(modq) is solvable for α ∈ FNq . So choose v to contain 0’s in the first t coordinates and 1’s in the remaining N − t coordinates;thensolvetoobtainavectorα=(α1,…,αN). Finally,reinterprettheαi’sasintegers from 0 to q − 1 rather than elements of Fq, and set the polynomial hq to be
􏰕N i=1
It is clear that hq so defined satisfies property (i). To see that it satisfies (ii), notice that the last N − t rows of B are unit vectors. Hence, even over Fq, any solution to the system Bα ≡ v (mod q) mustsetαt+1 =···=αN =1.
We wish to generalize Lemma 6.5 to the case where the modulus q is not necessarily prime. To do so, we will need two standard number theory facts, which we prove for completeness.
Proposition 6.6 (Hensel Lifting) Let B be an N ×N integer matrix, and suppose B is invertible mod q for some prime q. Then the system Bα ≡ v (mod qe) has a solution in α ∈ ZN for every v∈ZN ande∈N.
From this we want to construct a solution α′ to Bα′ ≡ v 􏰃mod qe+1􏰄. formα′=α+qeβforsomeβ∈ZN. Tofindβ,noticethat
Bα′ =B(α+qeβ) = Bα + qeBβ
= v + qec + qeBβ = v + qe (c + Bβ) .
Our solution will have the
hq (x) :=
αiδi (x) .
Proof. By induction on e. When e = 1 the proposition obviously holds, so assume it holds for e. Then there exists a solution α to Bα ≡ v(modqe), meaning that Bα−v = qec for some c ∈ ZN.
Thus, it suffices to find a β such that Bβ ≡ −c(modq). Since B is invertible mod q, such a β exists.
Proposition 6.7 (Chinese Remaindering) Let K and L be relatively prime. Then there exist integers a,b ∈ [KL] such that:
(i) For all x,y,z, the congruence z ≡ ax+by(modKL) holds if and only if z ≡ x(modK) and z ≡ y (mod L).
(ii) Ifx=y=1,thenax+by=KL+1asaninteger.
32

Proof. Let K′ and L′ be integers in [KL] such that K′ ≡ K−1 (mod L) and L′ ≡ L−1 (mod K); note that these exist since K and L are relatively prime. Then we simply need to set a := LL′ and b := KK′.
We can now prove the promised generalization of Lemma 6.5.
Lemma 6.8 Let y ,…,y be points in Zn, let Q be an integer, and let Q = qe1 ···qem be its prime
1t 1m factorization. Then there exists a multilinear polynomial hQ : Zn → Z such that
(i) hQ (yi) ≡ 0(modQ) for all i ∈ [t], and
(ii) hQ (z) = 1 for at least 2n − mt Boolean points z.
Proof. Say that a multilinear polynomial h : Zn → Z is (K, r)-satisfactory if (i’) h(yi) ≡ 0(modK) for all i ∈ [t], and
(ii’) h (z) = 1 for at least 2n − r Boolean points z.
Recallthatifqisprime,thenLemma6.5yieldsa(q,t)-satisfactorypolynomialhq. Furthermore, the coefficients (α1, . . . , αN ) of hq were obtained by solving a linear system Bα ≡ b (mod q) where B was invertible mod q.
First, suppose K = qe is a prime power. Then by Proposition 6.6, we can “lift” the solution α ∈ Zn of Bα ≡ b(modq) to a solution α′ ∈ Zn of Bα′ ≡ v(modK). Furthermore, after we perform this lifting, we still have α′t+1 = · · · = α′N = 1, since the matrix B has not changed (and in particular contains the identity submatrix). So if we set
􏰕N i=1
then hK is (K, t)-satisfactory.
Now let K and L be relatively prime, and suppose we found a (K, r)-satisfactory polynomial hK
as well as an (L, r′)-satisfactory polynomial hL. We want to combine hK and hL into a (KL, r + r′)- satisfactory polynomial hKL. To do so, we use Chinese remaindering (as in Proposition 6.7) to find an affine linear combination
hKL(x):=ahK (x)+bhL(x)−KL
(i”) hKL (x) ≡ 0(modKL) if and only if hK (x) ≡ 0(modK) and hL (x) ≡ 0(modL), and
(ii”) ifhK(x)=1andhL(x)=1thenhKL(x)=1.
Since there are at least 2n − (r + r′) Boolean points z such that hK (z) = hL (z) = 1, this yields a (KL, r + r′)-satisfactory polynomial as desired.
such that
hK (x) :=
α′iδi (x)
Thus, given any composite integer Q = qe1 ···qem, we can first use Hensel lifting to find a 1m
(qei,t)-satisfactorypolynomialhqi foreveryi∈[m],andthenuseChineseremainderingtocombine i
the hqi ’s into a (Q, mt)-satisfactory polynomial hQ.
We are finally ready to prove the integer analogue of Lemma 4.3.
33

Lemma 6.9 Let y1,…,yt be points in Zn, such that size(yi) ≤ s for all i ∈ [t]. Then for at least 2n − 2t2s Boolean points w ∈ {0, 1}n, there exists a multiquadratic polynomial p : Zn → Z such that
(i) p(yi)=0 for all i∈[t], (ii) p (w) = 1, and
(iii) p(z) = 0 for all Boolean z ̸= w.
Proof. Assume t ≤ 2n, since otherwise the lemma is trivial.
Let hQ : Zn → Z be the multilinear polynomial from Lemma 6.8, for some integer Q to be
specified later. Then our first claim is that there exists a multilinear polynomial g : Qn → Q, with rational coefficients, such that
(i’) g(yi) = hQ (yi) for all i ∈ [t], and
(ii’) g (z) = 0 for at least 2n − t Boolean points z.
This claim follows from linear algebra: we know the requirements g (yi) = hQ (yi) for i ∈ [t] are mutually consistent, since there exists a multilinear polynomial, namely hQ, that satisfies them. So if we write g in the basis of δz’s, as follows:
g(x)= 􏰕 g(z)δz(x) z∈{0,1}n
then condition (i’) gives us t′ independent affine constraints on the 2n coefficients g (z), for some t′ ≤ t. This means there must exist a solution g such that g (z) = 0 for at least 2n − t′ Boolean points z. Let z1, . . . , zt′ be the remaining t′ Boolean points.
Notice that z1,…,zt′ can be chosen independently of hQ. This is because we simply need to find t′ Boolean points z1,…,zt′, such that any “allowed” vector (hQ (y1),…,hQ (yt)) can be written as a rational linear combination of vectors of the form 􏰃δzj (y1) , . . . , δzj (yt)􏰄 with j ∈ [t′].
We now explain how Q is chosen. Let Γ be a t×t′ matrix whose rows are labeled by y1,…,yt, whose columns are labeled by z1, . . . , zt′ , and whose (i, j) entry equals δzj (yi). Then since we had t′ independent affine constraints, there must be a t′ × t′ submatrix Γ′ of Γ with full rank. We set Q := |det (Γ′)|.
With this choice of Q, we claim that g is actually an integer polynomial. It suffices to show that g (zj) is an integer for all j ∈ [t′], since the value of g at any x ∈ Zn can be written as an integer linear combination of its values on the Boolean points. Note that the vector (g(z1),…,g(zt′)) is obtained by applying the matrix (Γ′)−1 to some vector (v1, . . . , vt′ ) whose entries are hQ (yi)’s. Now, every entry of (Γ′)−1 has the form k/Q, where k is an integer; and since hQ (yi) ≡ 0 (mod Q) for all i ∈ [t], every vi is an integer multiple of Q. This completes the claim.
34

Also, since size (yi) ≤ s for all i ∈ [t], we have the upper bound
Q = 􏰅􏰅det􏰖􏰃Γ′􏰄􏰅􏰅
􏰎n 􏰏t′
≤ t′! (|yi| + 1)
􏰏t
≤ tt
≤ tt2ts
≤ 22ts.
i=1
􏰎􏰖n
(|yi| + 1) = 2ts+t log2 t
i=1
Here the last line uses the assumption that log2 t ≤ n, together with the fact that n ≤ s. Therefore Q can have at most 2ts distinct prime factors. So by Lemma 6.8, we have hQ (z) = 1
for at least 2n − 2t2s Boolean points z.
Putting everything together, if we define m (x) := hQ (x) − g (x), then we get a multilinear
polynomial m : Zn → Z such that (i”) m(yi)=0foralli∈[t],and
(ii”) m (z) = 1 for at least 2n − 2t2s Boolean points z.
Then for any w ∈ {0, 1}n with m (w) = 1, we can get a multiquadratic polynomial p : Zn → Z satisfying conditions (i)-(iii) of the lemma by taking p (x) := m (x) δw (x).
Lemma 6.9 easily implies a lower bound on the deterministic query complexity of the OR function.
􏰆􏰛 􏰇
Theorem 6.10 D􏰱s,2 (OR) = Ω 2n/s for all s. 􏰛
Proof. Let Y be the set of points queried by a deterministic algorithm, and assume size (y) ≤ s for all y ∈ Y. Then provided 2n − 2 |Y|2 s > 0 (or equivalently |Y| < 2n−1/s), Lemma 6.9 implies that there exists a multi􏰱quadratic extension polynomial A􏰱 : Zn → Z such that A􏰱(y) = 0 for all y ∈ Y, but nevertheless A (w) = 1 for some Boolean point w. So even if the algorithm is adaptive, we can let Y be the set of points it queries assuming each query is answered with 0, and then find A􏰱,B􏰱 such that A􏰱(y) = B􏰱(y) = 0 for all y ∈ Y, but nevertheless A􏰱 and B􏰱 lead to different values of the OR function. As mentioned before, one can calculate that the polynomial p from Lemma 6.9 satisfies size (p (x)) = O (size (x) + ts). For algebrization purposes, the key question is whether the dependence on t and scanbeeliminated,andreplacedbysomefixedpolynomialdependenceonsize(x)andn. Another interesting question is whether one can generalize Lemma 6.9 to queries of unbounded size—that is, whether the assumption size (yi) ≤ s can simply be eliminated. 7 Applications to Communication Complexity In this section, we give two applications of our algebrization framework to communication com- plexity: 35 (1) A new connection between communication complexity and computational complexity, which implies that certain plausible communication complexity conjectures would imply NL ̸= NP. (2) MA-protocols for the Disjointness and Inner Product problems with total communication cost O(√ n log n), essentially matching a lower bound of Klauck [25]. Both of these results can be stated without any reference to algebrization. On the other hand, they arose directly from the “transfer principle” relating algebrization to communication complexity in Section 4.3. 7.1 Karchmer-Wigderson Revisited Two decades ago, Karchmer and Wigderson [24, 42] noticed that certain communication complexity lower bounds imply circuit lower bounds—or in other words, that one can try to separate complexity classes by thinking only about communication complexity. In this section we use algebrization to give further results in the same spirit. Let f : {0,1}N × {0,1}N → {0,1} be a Boolean function, and let x and y be inputs to f held by Alice and Bob respectively. By an IP-protocol for f, we mean a randomized communication protocol where Alice and Bob exchange messages with each other, as well as with an omniscient prover Merlin who knows x and y. The communication cost is defined as the total number of bits exchanged among Alice, Bob, and Merlin. If f (x, y) = 1, then there should exist a strategy of Merlin that causes Alice and Bob to accept with probability at least 2/3, while if f (x, y) = 0 no strategy should cause them to accept with probability more than 1/3. Lemma 7.1 Suppose f : {0, 1}N × {0, 1}N → {0, 1} is in NL. Then f has an IP-protocol with communication cost O(polylogN). Proof. Let N = 2n. Then we can define a Boolean function A : {0,1}n+1 → {0,1}, such that the truth table of A (0x) corresponds to Alice’s input, while the truth table of A (1x) corresponds to Bob’s input. Taking n as the input􏰲length, we then have f ∈ PSPACEA[poly]. By Theorem 3.7 we have PSPACEA[poly] ⊆ IPA􏰲, where A is the multilinear extension of A. Hence f ∈ IPA􏰲. But by Theorem 4.11, this means that f admits an IP-protocol with communication cost O (poly n) = O (polylog N ). An immediate consequence of Lemma 7.1 is that, to prove a problem is outside NL, it suffices to lower-bound its IP communication complexity: Theorem 7.2 Let Alice and Bob hold 3SAT instances φA,φB respectively of size N. Suppose there is no IP-protocol with communication cost O (polylog N ), by which Merlin can convince Alice and Bob that φA and φB have a common satisfying assignment. Then NL ̸= NP. Likewise, to prove a problem is outside P, it suffices to lower-bound its RG communication complexity, where RG is the Refereed Games model of Feige and Kilian [12] (with a competing yes-prover and no-prover). In this case, though, the EXP = RG theorem is not only algebrizing but also relativizing, and this lets us prove a stronger result: Theorem 7.3 Let φ be a 3SAT instance of size N. Suppose there is no bounded-error randomized verifier that decides whether φ is satisfiable by (i) making O (polylog N ) queries to a binary encoding of φ, and 36 (ii) exchanging O (polylog N ) bits with a competing yes-prover and no-prover, both of whom know φ and can exchange private messages not seen by the other prover. Then P ̸= NP. Proof. Suppose P = NP. Then by padding, EXPA[poly] = NEXPA[poly] for all oracles A. As discussed in Section 3.5, the work of Feige and Kilian [12] implies that EXPA[poly] = RGA for all oracles A. Hence NEXPA[poly] = RGA as well. In other words, given oracle access to an exponentially large 3SAT instance φ, one can decide in RG whether φ is satisfiable. Scaling down by an exponential now yields the desired result. 7.2 Disjointness and Inner Product In this subsection we consider two communication problems. The first is Disjointness, which was defined in Section 4.3. The second is Inner Product, which we define as follows. Alice and Bob are given n-bit strings x1 . . . xn and y1 . . . yn respectively; then their goal is to compute 􏰕n i=1 as an integer. Clearly Disjointness is equivalent to deciding whether IP (x,y) = 0, and hence is reducible to Inner Product. √ Klauck [25] showed that any MA-protocol for Disjointness has communication cost Ω ( n). The “natural” conjecture would be that the √n was merely an artifact of his proof, and that a more refined argument would yield the optimal lower bound of Ω (n). However, using a protocol inspired by our algebrization framework, we are able to show that this conjecture is false. Theorem 7.4 There exist MA-protocols for the Disjointness and Inner Product problems, in which Alice receives an O (√n log n)-bit witness from Merlin and an O (√n log n)-bit message from Bob. Proof. As observed before, it suffices to give a protocol for Inner Product; a protocol for Disjoint- ness then follows immediately. Assume n is a perfect square. Then Alice and Bob can be thought of as holding functions a : [√n] × [√n] → {0, 1} and b : [√n] × [√n􏰕] → {0, 1} respectively. Their goal is to compute the inner product IP := a(x,y)b(x,y). x,y∈[√n] Choose a prime q ∈ [n,2n]. Then a a􏰕nd b have unique extensions 􏰲a : F2q → Fq and 􏰲b : F2q → Fq respectively as degree-(√n − 1) polynomials. Also, define the polynomial s : Fq → Fq by √n s(x):= 􏰲a(x,y)􏰲b(x,y) (mod q). 􏰕√n x=1 IP (x,y) := xiyi y=1 n−1). Notice that deg (s) ≤ 2 (√ Merlin’s message to Alice consists of a polynomial s′ : Fq → Fq, which also has degree at most 2 (√n − 1), and which is specified by its coefficients. Merlin claims that s = s′. If Merlin is honest, then Alice can easily compute the inner product as IP = s(x). 37 Sotheproblemreducestocheckingthats=s′. Thisisdoneas􏰲follows:firstBobchoosesr∈Fq uniformly at random and sends it to Alice, along with the value of b (r, y) for every y ∈ [√n]. Then Alice checks that 􏰕√ n 􏰲a(r,y)􏰲b(r,y) (mod q). Pr 􏰥s(r)=s′(r)􏰦≤deg(s)≤1, s′(r)= If s = s′, then the above test succeeds with certainty. On the other hand, if s ̸= s′, then y=1 r∈Fq q3 and hence the test fails with probability at least 2 . 3 Let us make two remarks about Theorem 7.4. 􏰲 √ First, we leave as an open problem whether one could do even better than O ( n) by using an AM-protocol: that is, a protocol in which Alice (say) can send a single random challenge to Merlin and receive a response. (As before, the communication cost is defined as the sum of the lengths of all messages between Alice, Bob, and Merlin.) On the other hand, it is easy to generalize Theorem 7.4 to give an MAM-protocol (one where first Merlin sends a message, then Alice, then Merlin) with complexity O 􏰃n1/3 log n􏰄. Similarly, one can give an MAMAM-protocol with complexity O 􏰃n1/4 log n􏰄, an MAMAMAM-protocol with complexity O 􏰃n1/5 log n􏰄, and so on. In the limit of arbitrarily many rounds, one gets an IP-protocol with complexity O (log n log log n). Second, one might wonder how general Theorem 7.4 is. In particular, can it be extended to g􏰲ive an MA-protocol for every predicate f : {0, 1}n × {0, 1}n → {0, 1} with total communication O (√n)? The answer is no, by a simple counting argument. We can assume without loss of generality that every MA-protocol has the following form: first Alice and Bob receive an m-bit message from Merlin; then they exchange T messages between themselves consisting of a single bit each. Let pt be the probability that the tth message is a ‘1’, as a function of the n + m + t − 1 bits (one player’s input plus Merlin’s message plus t − 1 previous messages) that are relevant at the tth step. It is not hard to see that each pt can be assumed to have the form i/n2, where i is an integer, with only negligible change to the acceptance probability. In that case there are 􏰃n2􏰄2n+m+t−1 choices for each function pt : {0, 1}n+m+t−1 → [0, 1], whence 􏰃n2􏰄2n+m 􏰃n2􏰄2n+m+1 ···􏰃n2􏰄2n+m+T−1 possible protocols. But if m + T = o (n), this product is still dwarfed by 222n , the number of distinct Boolean functions f : {0, 1}n × {0, 1}n → {0, 1}. Thus, Theorem 7.4 has the amusing consequence that the Inner Product function, which is often considered the “hardest” function in communication complexity, is actually unusually easy for MA-protocols. (The special property of Inner Product we used is that it can be written as a degree-2 polynomial in Alice’s and Bob’s inputs.) 8 Zero-Knowledge Protocols In searching complexity theory for potentially non-algebrizing results, it seems the main source is cryptography—and more specifically, cryptographic results that exploit the locality of computa- tion. These include the zero-knowledge protocol for NP due to Goldreich, Micali, and Wigderson [16] (henceforth the GMW Theorem), the two-party oblivious circuit evaluation of Yao [45], and potentially many others. Here we focus on the GMW Theorem. 38 As discussed in Section 1, the GMW Theorem is inherently non-black-box, since it uses the structure of an NP-complete problem (namely 3-Coloring). On the other hand, the way the theorem exploits that structure seems inherently non-algebraic: it does not involve finite fields or low-degree polynomials. Nevertheless, in this section we will show that even the GMW Theorem is algebrizing. Let us start by defining the class CZK, or Computational Zero Knowledge, as well as CZKA (that is, CZK with oracle access to A). Definition 8.1 A language L is in CZK if there exists a protocol in which a probabilistic polynomial- time verifier V interacts with a computationally-unbounded prover P, such that for all inputs x the following holds. • Completeness. If x ∈ L then P causes V to accept with probability 1. • Soundness. If x ∈/ L then no prover P ∗ can cause V to accept with probability more than 1/2. • Zero-Knowledge. If x ∈ L then there exists an expected polynomial-time simulator that, given black-box access13 to a polynomial-time verifier V ∗, produces a message transcript that cannot be efficiently distinguished from a transcript of an actual conversation between V ∗ and P. (In other words, the two probability distributions over message transcripts are computa- tionally indistinguishable.) We define CZKA to mean the version of CZK where all three machines—the prover, verifier, and simulator—have access to the oracle A. Then Goldreich et al. [16] proved the following: Theorem 8.2 (GMW Theorem) If one-way functions exist then NP ⊆ CZK. It is not hard to show that Theorem 8.2 is non-relativizing. Intuitively, given a black-box function f : {0, 1}n → {0, 1}, suppose a prover P wants to convince a polynomial-time verifier V that there exists a z such that f (z) = 1. Then there are two possibilities: either P can cause V to query f (z), in which case the protocol will necessarily violate the zero-knowledge condition (by revealing z); or else P can not cause V to query f (z), in which case the protocol will violate either completeness or soundness. By formalizing this intuition one can show the following: Theorem 8.3 There exists an oracle A relative to which (i) one-way functions exist (i.e. there exist functions computable in PA that cannot be inverted in BPPA on a non-negligible fraction of inputs), but (ii) NPA ̸⊂ CZKA. By contrast, we now show that the GMW Theorem is algebrizing. In proving this theorem, we will exploit the availability of a low-degree extension A􏰲 to make the oracle queries zero-knowledge. 13CZK can also be defined in a way that allows non-black-access (i.e., access to the verifier’s source code). However, our protocol, like the original GMW one, will only require black-box access. 39 Theorem 8.4 Let A be an oracle and let A􏰲 be any extension of A. Suppose there exists a one- A􏰲 􏰲 A􏰲 way function, computable in P , which cannot be inverted with non-negligible probability by BPP adversaries. Then NPA ⊆ CZKA. 􏰲􏰲􏰲n􏰲 Proof. We will assume for simplicity that the extension A is just a polynomial A : F → F over a fixed finite field F, which extends a Boolean function A : {0, 1}n → {0, 1}. Also, let d = deg(A), and assume d ≪ char (F). (The proof easily generalizes to the case where A and A are as defined in Section 2.) Deciding whether an NPA machine accepts is equivalent to deciding the satisfiability of a Boolean formula φ (w1, . . . , wm), which consists of a conjunction of two types of clauses: (i) Standard 3SAT clauses over the variables w1, . . . , wm. (ii) “Oracle clauses,” each of which has the form yi = A (Yi), where Yi ∈ {0, 1}n is a query to A (composed of n variables wj1,...,wjn) and yi is its expected answer (composed of another variable wjn+1 ). Given such a formula φ, our goal is to convince a BPPA􏰲 verifier that φ is satisfiable, without revealing anything about the satisfying assignment w1, . . . , wm (or anything else). To achieve this, we will describe a constant-round zero-knowledge protocol in which the verifier accepts with probability 1 given an honest prover, and rejects with probability Ω (1/ poly (n)) given a cheating prover. Given any such protocol, it is clear that we can increase the soundness gap to Ω (1), by repeating the protocol poly (n) times. Let us describe our protocol in the case that the prover and verifier are both honest. In the first round, the prover uses the one-way function to send the verifier commitments to the following ob jects: • A satisfying assignment w1,...,wm for φ. • A random nonzero field element r ∈ F. • For each oracle clause yi = A(Yi), – A random affine function Li : F → Fn (in other words, a line) such that Li (0) = Yi and Li (1) ̸= Yi. 􏰲 – Apolynomialpi :F→F,ofdegreeatmostd,suchthatpi(t)=A(Li(t))forallt∈F. Given these objects, the verifier can choose randomly to perform one of the following four tests: (1) Ask the prover for a zero-knowledge proof that the standard 3SAT clauses are satisfied. (2) Choose a random oracle clause yi = A (Yi), and ask for a zero-knowledge proof that Li (0) = Yi. (3) Choose a random oracle clause yi = A (Yi), and ask for a zero-knowledge proof that pi (0) = yi. (4) Choose a random oracle clause yi = A (Yi) as well as a random nonzero field element s ∈ F. Ask for the value u of Li (rs), as well as a zero-knowledge proof that u = Li (rs). Query A􏰲 (u). Ask for a zero-knowledge proof that pi (rs) = A􏰲 (u). 40 To prove the correctness of the above protocol, we need to show three things: completeness, zero-knowledge, and soundness. Completeness: This is immediate. If the prover is honest, then tests (1)-(4) will all pass with probability 1. Zero-Knowledge: Let V ∗ be any verifier. We will construct a simulator to create a transcript which is computationally indistinguishable from its communication with the honest prover P . The simulator first chooses random values for the wi’s (which might not be satisfying at all) and commits to them. It also commits to a random r ∈ F∗. For tests (1)-(3), the simulator acts as in the proof of the GMW Theorem [16]. So the interesting test is (4). First note that rs is a random nonzero element, regardless of how V ∗ selected s. Now the key observation is that Li (rs), the point at which the verifier queries A􏰲, is just a uniform random point in Fn􏰰 {Yi}. Thus, we can construct a simulator as follows: if the verifier is going to ask the prover a􏰲bout an oracle clause yi = A (Yi), then first choose a point Xi ∈ Fn uniformly at random and query A(Xi). (The probability that Xi will equal Yi is negligible.) Next choose nonzero field elements r,s ∈ F uniformly at random. Let Li be the unique line such􏰲that Li (0) = Yi and Li (rs) = Xi, and let pi be the unique degree-d polynomial such that pi (t) = A (Li (t)) for all t ∈ F (which can be found by interpolation). Construct commitments to all of these objects. Assuming the underlying commitment scheme is secure against BPPA􏰲 machines, the resulting probability distribution over messages will be computationally indistinguishable from the actual distribution. Soundness: Suppose the NPA machine rejects. Then when the prover sends the verifier a commitment to the “satisfying assignment” w1,...,wm, some clause C of φ will necessarily be unsatisfied. If C is one of the standard 3SAT clauses, then by the standard GMW Theorem, the prover will be caught with Ω (1/ poly (n)) probability when the verifier performs test (1). So the interesting case is that C is an oracle clause yi = A (Yi). In this case, since the truth is that yi ̸= A (Yi), at least one of the following must hold: (i) yi ̸= pi (0), (ii) pi (0) ̸= A􏰲 (Li (0)), or (iii) A􏰲(Li(0))̸=A(Yi). If (i) holds, then the prover will be caught with Ω(1/poly(n)) probability when the verifier performs test (3). If (ii) holds, then the two degree-d polynomials pi (t) and A􏰲(Li (t)) must differ on at least a 1 − d/ char (F) fraction of points t ∈ F. Hence, since rs is a random nonzero element of F conditioned only on s being random, the prover will be caught with Ω(1/poly(n)) probability when the verifier performs test (4). If (iii) holds, then Li (0) ̸= Yi. Hence the prover will be caught with Ω (1/ poly (n)) probability when the verifier performs test (2). Let us make two remarks about Theorem 8.4. (1) Notice that in our zero-knowledge protocol, the prover’s strategy can actually be implemented in BPPA􏰲, given a satisfying assignment w1, . . . , wm for the formula φ. (2) Although our protocol needed poly (n) rounds to achieve constant soundness (or O (1) rounds to achieve 1/poly(n) soundness), we have a variant that achieves constant soundness with a constant number of rounds. For the non-oracle part of the protocol, it is well-known how 41 to do this. To handle oracle queries, one composes the polynomially many queries that the verifier selects among by passing a low-degree curve through them. This reduces the case (4) to a single random query on this curve. We omit the details. 9 The Limits of Our Limit Some would argue with this paper’s basic message, on the grounds that we already have various non-relativizing results that are not based on arithmetization. Besides the GMW protocol (which we dealt with in Section 8), the following examples have been proposed: (1) Small-depth circuit lower bounds, such as AC0 ̸= TC0 [32], can be shown to fail relative to suitable oracle gates. (2) Arora, Impagliazzo, and Vazirani [3] argue that even the Cook-Levin Theorem (and by ex- tension, the PCP Theorem) should be considered non-relativizing. (3) Hartmanis et al. [17] cite, as examples of non-relativizing results predating the “interactive proofs revolution,” the 1977 result of Hopcroft, Paul, and Valiant [19] that TIME (f (n)) ̸= SPACE (f (n)) for any space-constructible f , as well as the 1983 result of Paul et al. [29] that TIME (n) ̸= NTIME (n). Recent time-space tradeoffs for SAT (see van Melkebeek [28] for a survey) have a similar flavor. There are two points we can make regarding these examples. Firstly, the small-depth circuit lower bounds are already “well covered” by the natural proofs barrier. Secondly, because of subtleties in defining the oracle access mechanism, there is legitimate debate about whether the results listed in (2) and (3) should “truly” be considered non-relativizing; see Fortnow [13] for a contrary perspective.14 Havingsaidthis,wedonotwishtobedogmatic. Ourresultstellusagreatdealaboutthefuture prospects for arithmetization, but about other non-relativizing techniques they are comparatively silent. 10 Beyond Algebrizing Techniques? In this section, we discuss two ideas one might have for going beyond the algebrization barrier, and show that some of our limitation theorems apply even to these ideas. 10.1 k-Algebrization One of the most basic properties of relativization is transitivity: if two complexity class inclusions C ⊆ D and D ⊆ E both relativize, then the inclusion C ⊆ E also relativizes. Thus, it is natural to ask whether algebrization is transitive in the same sense. We do not know the answer to this question, and suspect that it is negative. However, there is a kind of transitivity that holds. Given an oracle A, let a double-extension A􏰲􏰲 of A be an oracle produced by (1) taking a low-degree extension A􏰲 of A, 14Eric Allender has suggested the delightful term “irrelativizing,” for results that neither relativize nor fail to relativize. 42 (2) letting f be a Boolean oracle such that f (x, i) is the ith bit in the binary representation of A􏰲(x), and then (3) taking a low-degree extension A of f. 􏰲􏰲􏰲 Now, the above suggests one possible approach to defeating the algebrization barrier. Call a 􏰲􏰲 􏰲 complexity class inclusion C ⊆ D double-algebrizing if CA ⊆ DA for all A,A􏰲, triple-algebrizing if Alas, we now show that any proof of P ̸= NP will need to go outside the entire hierarchy. Theorem 10.2 Any proof of P ̸= NP will require techniques that are not merely non-algebrizing, but non-k-algebrizing for every constant k. Proof. Recall that in Theorem 5.1, we sh􏰲owed that any proof of P ̸= NP will require non- 􏰲􏰲 (One can similarly define a triple-extension A, and so on.) Then the following is immediate: Proposition 10.1 For all complexity classes C, D, E, if CA ⊆ DA􏰲 and DA ⊆ EA􏰲 for all A, A􏰲, then 􏰲􏰲 􏰲 C A ⊆ E A f o r a l l A , A􏰲 . 􏰲􏰲 􏰲 A A􏰲 􏰲􏰲 C ⊆ D for all A, A, and so on. Then any k-algebrizing result is also (k + 1)-algebrizing, but the converse need not hold. We thus get a whole infinite hierarchy of proof techniques, of which this paper studied only the first level. algebrizing techniques, by giving oracles A, A􏰲 such that NPA = PA = PSPACE. In that case, A was any PSPACE-complete language, while A was the unique multilinear extension of A, which is also PSPACE-complete by Babai, Fortnow, and Lund [4]. Now let A􏰲 be the multilinear extension 􏰲 􏰲􏰲 􏰲 of the binary representation of A. Then A is also PSPACE-complete by Babai et al. Hence 􏰲􏰲 􏰲􏰲 NPA = PA = PSPACE. The same is true inductively for A and so on. 􏰲􏰲 Similarly, any proof P ̸= PSPACE will require techniques that are non-k-algebrizing for every k. On the other hand, for most of the other open problems mentioned in this paper—P versus RP, NEXP versus P/poly, and so on—we do not know whether double-algebrizing techniques already We have shown that arithmetization—“lifting” Boolean logic operations to arithmetic operations over the integers or a field—will not suffice to solve many of the open problems in complexity theory. A natural question is whether one could evade our results by lifting to other algebras, particularly non-commutative ones. Unfortunately, we now explain why our limitation theorems extend with little change to associative algebras with identity over a field. This is a very broad class that includes matrix algebras, quaternions, Clifford algebras, and more. The one constraint is that the dimension of the algebra (or equivalently, the representation size of the elements) should be less than exponential in n.15 15This is similar to the requirement that the integers should not be too large in Section 6. 43 suffice. That is, we do not know whether there exist A, A such that RPA ̸⊂ PA, NEXPA ⊂ PA/poly, and so on. Thus, of the many open problems that are beyond the reach of arithmetization, at least some could conceivably be solved by “k-arithmetization.” 10.2 Non-Commutative Algebras 􏰲􏰲 􏰲􏰲 􏰲􏰲 Formally, an algebra over the field F is a vector space V over F, which is equipped with a multiplication operation V ·V → V such that u(v+w) = uv+uw for all u,v,w ∈ V. The algebra is associative if its multiplication is associative, and has identity if one of its elements is a multiplicative identity. The dimension of the algebra is the dimension of V as a vector space. A crucial observation is that every k-dimensional associative algebra over F is isomorphic to a subalgebra of Mk (F), the algebra of k × k matrices with entries in the field F. The embedding is the natural one: every element v ∈ V defines a linear transformation Mv via Mv x = v · x. We will now explain why, for associative algebras with identity, our main results go through almost without change. For notational simplicity, we will state our results in terms of the full matrix algebra Mk (F), though the results would work just as well for any subalgebra of Mk (F) containing the zero and identity elements. Given a polynomial p : Mk (F)n → Mk (F), call p sorted-multilinear if it has the form p(X1,...,Xn)= 􏰕 aS􏰖Xi, S ⊆[n] i∈S where the coefficients aS belong to F, and all products are taken in order from X1 to Xn. Now letnIk be the k × k identity matrix and 0k be the all-zeroes matrix. Also, call a point Z ∈ Mk (F) Boolean if every coordinate is either Ik or 0k, and let 􏰖n i=1 be the unique sorted-multilinear polynomial such that δZ (Z) = Ik and δZ (W) = 0k for all Boolean W ̸= Z. Then just as in the commutative case, every sorted-multilinear polynomial m has a unique representation in the form 􏰕 m(X) = mZδZ (X) Z ∈{0k ,Ik }n δZ (X):= [ZiXi +(Ik −Zi)(Ik −Xi)] Also, every Boolean function f : f􏰲 ( X ) = f ( Z ) δ Z ( X ) Z∈{0k,Ik}n as a sorted-multilinear polynomial. Provided k = O(poly(n)), it is easy to show that any proof of P ̸= NP will require “non- commutatively non-algebrizing techniques.” Once again, we can let A be any PSPACE-complete language, and let A􏰲 be the unique sorted-multilinear exte􏰲nsion of A over Mk (F). Then the observations of Babai, Fortnow, and Lund [4] imply that A is also computable in PSPACE, and hence NPA􏰲 = PA = PSPACE. We can also repeat the separation results of Sections 4 and 5 in the non-commutative setting. Rather than going through every result again, we will just give one illustrative example. We will show that, given a non-commutative extension A􏰲 : Mk (F)n → Mk (F) of a Boole􏰲an function A : {0k,Ik}n → {0k,Ik}, any deterministic algorithm needs Ω􏰃2n/k2􏰄 queries to A to find a Boolean point W ∈ {0k,Ik}n such that A(W) = Ik. (Note that switching from fields to k × k matrix algebras causes us to lose a factor of k2 in the bound.) The first step is to prove a non-commutative version of Lemma 4.2. 44 where mZ is a coefficient in F such that m(Z) = mZIK. {0k,Ik}n → {0k,Ik} has a unique extension 􏰕 Lemma 10.3 Let Y1, . . . , Yt be any points in Mk (F)n. Then there exists a sorted-multilinear polynomial m : Mk (F)n → Mk (F) such that (i) m(Yi)=0k for all i∈[t], and (ii) m(W)=Ik for at least 2n −k2t Boolean points W ∈{0k,Ik}n. Proof. If we represent m as 􏰕 m(X) = mZδZ (X), Z ∈{0k ,Ik }n then the constraint m(Yi) = 0k for all i ∈ [t] corresponds to k2t linear equations relating the 2n coefficients mZ. By basic linear algebra, it follows that there must be a solution in which at least 2n − k2t of the coefficients are equal to Ik, and hence m(W) = Ik for at least 2n − k2t Boolean points W. Using Lemma 10.3, we can also prove a non-commutative version of Lemma 4.3. Lemma 10.4 Let Y1, . . . , Yt be any points in Mk (F)n. Then for at least 2n − k2t Boolean points W ∈ {0k,Ik}n, there exists a multiquadratic polynomial p : Mk (F)n → Mk (F) such that (i) p(Yi)=0k for all i∈[t], (ii) p(W)=Ik,and (iii) p(Z) = 0k for all Boolean Z ̸= W. Proof. Let m : Mk (F)n → Mk (F) be the sorted-multilinear polynomial from Lemma 10.3, and pick any Boolean W such that m(W) = Ik. Then a multiquadratic polynomial p satisfying properties (i)-(iii) can be obtained from m as follows: p(X) := m(X)δW (X). Lemma 10.4 immediately gives us a non-commutative version of Theorem 4.4, the lower bound on deterministic query complexity of the OR function. 􏰲 􏰃 n 􏰲2􏰄 Theorem 10.5 DMk(F),2 (OR) = Ω 2 /k for every matrix algebra Mk (F). By using Theor􏰲em 10.5, for every k = O (poly (n)) one can construct an oracle A, and a k × k matrix extension A of A, such that NPA ̸⊂ PA. This then implies that any resolution of the P versus NP problem will require “non-commutatively non-algebrizing techniques.” 11 Conclusions and Open Problems Arithmetization is one of the most powerful ideas in complexity theory. It led to the IP = PSPACE Theorem, the PCP Theorem, non-relativizing circuit lower bounds, and many other achievements of the last two decades. Yet we showed that arithmetization is fundamentally unable to resolve many of the barrier problems in the field, such as P versus NP, derandomization of RP, and circuit lower bounds for NEXP. 45 Can we pinpoint what it is about arithmetization that makes it incapable of solving these problems? In our view, arithmetization simply fails to “open the black box wide enough.” In a typical arithmetization proof, one starts with a polynomial-size Boolean formula φ, and uses φ to produce a low-degree polynomial p. But having done so, one then treats p as an arbitrary black-box function, subject only to the constraint that deg (p) is small. Nowhere does one exploit the small size of φ, except insofar as it lets one evaluate p in the first place. The message of this paper has been that, to make further progress, one will have to probe φ in some “deeper” way. To reach this conclusion, we introduced a new model of algebraic query complexity, which has already found independent applications in communication complexity, and which has numerous facets to explore in its own right. We now propose five directions for future work, and list some of the main open problems in each direction. (1) Find non-algebrizing techniques. This, of course, is the central challenge we leave. If arithmetization—which embeds the Boolean field F2 into a larger field or the integers—is not enough, then a natural idea is to embed F2 into a “richer” algebra. But in Section 10.2 we showed that for every subexponential k, the algebra of k × k matrices is still not “sufficiently rich.” So the question arises: what other useful algebraic structures can mathematics offer complexity theory? Another possible way around the algebrization barrier is “recursive arithmetization”: first arith- metizing a Boolean formula, then reinterpreting the result as a Boolean function, then arithmetizing that function, and so on ad infinitum. In Section 10.1, we showed that k-arithmetization is not powerful enough to prove P ̸= NP for any constant k. But we have no idea whether double- arithmetization is already powerful enough to prove P = RP or NEXP ̸⊂ P/poly. (2) Find ways to exploit the structure of polynomials produced by arithmetization. This is also a possible way around the algebrization barrier, but seems important enough to deserve itsownheading. Thequestionis:g􏰲iventhatapolynomialA􏰲:Fn→Fwasproducedbyarithmetiz- ing a small Boolean formula, does A have any properties besides low degree that a polynomial-time algorithm querying it could exploit? Or alternatively, do there exist “pseudorandom extensions” 􏰲n􏰲 A : F → F—that is, low-degree extensions that are indistinguishable from “random” low-degree extensions by any BPPA machine, but that were actually produced by arithmetizing small Boolean formulas? As a hint of how the structure of A􏰲 might be exploited, let us point out that, if A􏰲 was produced by arithmetizing a 3SAT formula φ, then one can actually recover φ in polynomial time by making oracle queries to A􏰲.16 (3) Find open problems that can still be solved with algebrizing techniques. In the short term, this is perhaps the most “practical” response to the algebrization barrier. Here is a problem that, for all we know, might still be solvable with tried-and-true arithmetization methods: improve the result of Santhanam [36] that PromiseMA ̸⊂ SIZE􏰃nk􏰄 to MA ̸⊂ SIZE􏰃nk􏰄. 16The algorithm is as follows. Assume for simplicity that every clause of φ contains exactly 3 literals. Then for each triple of variables (xi,xj,xk): (1) Set the remaining n − 3 variables to constants. (2) Query A􏰲 on O(deg(A􏰲)3) values of xi,xj,xk, then use interpolation to recover a trivariate polynomial p(xi,xj,xk). (3) Try to divide p by each of the eight multilinear polynomials (1−xixjxk, 1−xixj (1 − xk), etc.) corresponding to the possible 3SAT clauses involving xi,xj,xk. Whenever such a polynomial divides p, we have learned another clause of φ. The only thing to be careful about is that, in setting the remaining n − 3 variables to constants, we do not inadvertently set p (xi , xj , xk ) = 0. But this is easily arranged. 46 (4) Prove algebraic oracle separations. Can we show that the interactive protocol of Lund, Fortnow, Karloff, and Nisan [27] cannot be made constant-round by any algebrizing tech- nique? In other words, can we give an oracle A and extension A􏰲 such that coNPA ̸⊂ AMA􏰲? In the communication complexity setting, Klauck [25] mentions coNP versus AM as a difficult open problem; perhaps the algebraic query version is easier. The larger challenge is to give algebraic oracles that separate all the levels of the polyno- mial hierarchy—or at least separate the polynomial hierarchy from larger classes such as P#P and PSPACE.17 In the standard oracle setting, these separations were achieved by Furst-Saxe-Sipser [15] and Yao [44] in the 1980’s, whereas in the communication setting they remain notorious open problems. Again, algebraic query complexity provides a natural intermediate case between query complexity and communication complexity. Can we show that non-algebrizing techniques would be needed to give a Karp-Lipton collapse to MA? Or give an interactive protocol for coNP where the prover has the power of NP? Can􏰲we show that a BQPA􏰲 or MAA􏰲 machine needs exponentially many queries to the extension oracle A, not only to solve the Disjointness problem, but also just to find a Boolean point x such that A􏰲(x) = 1? Also, in the integers case, can we show that a PA􏰱 machine needs exponentially many queries to A􏰱 to find an x such that A􏰱(x) = 1? (That is, can we remove the technical limitations of Theorem 6.10 regarding the size of the inputs and outputs?) (5) Understand algebrization better. In defining what it meant for inclusions and sepa- rations to algebrize, was it essential to give only one machine access to the extension oracle A􏰲, and the other access to A? Or could we show (for example) not only that coNPA ⊆ IPA􏰲, but also that A􏰲 A􏰲 A􏰲 􏰲 A 􏰃 k 􏰄 A􏰲 A􏰲 􏰲􏰃 k 􏰄 coNP ⊆ IP ? What about improving the separation PP ̸⊂ SIZE n to PP ̸⊂ SIZE n ? Likewise, can we improve the separation MAA􏰲 ̸⊂ PA/poly to MAA[poly] ̸⊂ PA/poly? EXP EXP Are there complexity cla􏰱sses C and D that can be separated by a finite field extension A, but not by an integer extension A? Are there complexity classes that can be separated in the algebraic oracle setting, but not the communication setting? Low-degree extensions can be seen as just one example of an error-correcting code. To what extent do our results carry over to arbitrary error-correcting codes? Arora, Impagliazzo, and Vazirani [3] showed that contrary relativizations of the same statement (for example, PA = NPA and PB ̸= NPB) can be interpreted as proving independence from a certain formal system. Can one interpret contrary algebrizations the same way? Acknowledgments We thank Benny Applebaum, Sanjeev Arora, Boaz Barak, Andy Drucker, Lance Fortnow, Russell Impagliazzo, Hartmut Klauck, Adam Klivans, Ryan O’Donnell, Rahul Santhanam, Sasha Sherstov, Amir Shpilka, Madhu Sudan, Luca Trevisan, and Ryan Williams for helpful discussions. 17If the oracle A􏰲 only involves a low-degree extension over Fq, for some fixed prime q = o(n/logn), then we can 􏰲 A A􏰲 􏰂 􏰲 give A,A such that PP ̸⊂ PH . The idea is the following: let A be the unique multilinear extension of A over Fq. Clearly a PPA machine can decide whether x∈{0,1}n A(x) ≥ 2n−1. On the other hand, supposing a PHA􏰲 machine solved the same problem, we c􏰲ould interpret the universal quantifiers as AND gates, the existential quantifiers as OR gates, and the queries to A as summation gates modulo q. We could thereby obtain an AC0 [q] circuit of size 2poly(n), which computed the Boolean MAJORITY given an input of size 2n (namely, the truth table of A). But when q = o (n/ log n), such a constant-depth circuit violates the celebrated lower bound of Smolensky [38]. Unfortunately, the above argument breaks down when the field size is large compared to n—as it needs to be for most algorithms that would actually exploit oracle access to A􏰲. Therefore, it could be argued that this result is not “really” about algebrization. 47 References [1] S. Aaronson. Oracles are subtle but not malicious. In Proc. IEEE Conference on Computational Complexity, pages 340–354, 2006. ECCC TR05-040. [2] S. Aaronson and A. Ambainis. Quantum search of spatial regions. Theory of Computing, 1:47–79, 2005. quant-ph/0303041. [3] S. Arora, R. Impagliazzo, and U. Vazirani. Relativizing versus nonrelativizing techniques: the role of local checkability. Manuscript, 1992. [4] L. Babai, L. Fortnow, and C. Lund. Nondeterministic exponential time has two-prover inter- active protocols. Computational Complexity, 1(1):3–40, 1991. [5] T. Baker, J. Gill, and R. Solovay. Relativizations of the P=?NP question. SIAM J. Comput., 4:431–442, 1975. [6] C. H. Bennett and J. Gill. Relative to a random oracle A, PA ̸= NPA ̸= coNPA with probability 1. SIAM J. Comput., 10(1):96–113, 1981. [7] H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and compu- tation. In Proc. ACM STOC, pages 63–68, 1998. quant-ph/9702040. [8] H. Buhrman, L. Fortnow, and T. Thierauf. Nonrelativizing separations. In Proc. IEEE Con- ference on Computational Complexity, pages 8–12, 1998. [9] H. Buhrman, N. Vereshchagin, and R. de Wolf. On computation and communication with small bias. In Proc. IEEE Conference on Computational Complexity, pages 24–32, 2007. [10] H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Comput. Sci., 288:21–43, 2002. [11] A. K. Chandra, D. Kozen, and L. J. Stockmeyer. Alternation. J. ACM, 28(1):114–133, 1981. [12] U. Feige and J. Kilian. Making games short. In Proc. ACM STOC, pages 506–516, 1997. [13] L. Fortnow. The role of relativization in complexity theory. Bulletin of the EATCS, 52:229–244, February 1994. [14] L. Fortnow and A. R. Klivans. Efficient learning algorithms yield circuit lower bounds. J. Comput. Sys. Sci., 2008. To appear. Earlier version in Proceedings of COLT’2006, pages 350-363. [15] M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial time hierarchy. Math. Systems Theory, 17:13–27, 1984. [16] O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM, 38(1):691–729, 1991. [17] J. Hartmanis, R. Chang, S. Chari, D. Ranjan, and P. Rohatgi. Relativization: a revisionistic perspective. Bulletin of the EATCS, 47:144–153, 1992. [18] J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285–306, 1965. 48 [19] J. E. Hopcroft, W. J. Paul, and L. G. Valiant. On time versus space. J. ACM, 24(2):332–337, 1977. [20] R. Impagliazzo, V. Kabanets, and A. Wigderson. In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Sys. Sci., 65(4):672–694, 2002. [21] A. Juma, V. Kabanets, C. Rackoff, and A. Shpilka. The black-box query complexity of poly- nomial summation. ECCC TR07-125, 2007. [22] B. Kalyanasundaram and G. Schnitger. The probabilistic communication complexity of set intersection. SIAM J. Discrete Math, 5(4):545–557, 1992. [23] R. Kannan. Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control, 55:40–56, 1982. [24] M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Comput., 3:255–265, 1990. [25] H. Klauck. Rectangle size bounds and threshold covers in communication complexity. In Proc. IEEE Conference on Computational Complexity, pages 118–134, 2003. cs.CC/0208006. [26] A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput., 31:1501–1526, 2002. Earlier version in ACM STOC 1999. [27] C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. J. ACM, 39:859–868, 1992. [28] D. van Melkebeek. A survey of lower bounds for satisfiability and related problems. Founda- tions and Trends in Theoretical Computer Science, 2:197–303, 2007. ECCC TR07-099. [29] W. J. Paul, N. Pippenger, E. Szemer ́edi, and W. T. Trotter. On determinism versus non- determinism and related problems. In Proc. IEEE FOCS, pages 429–438, 1983. [30] R. Raz. Exponential separation of quantum and classical communication complexity. In Proc. ACM STOC, pages 358–367, 1999. [31] R. Raz and A. Shpilka. On the power of quantum proofs. In Proc. IEEE Conference on Computational Complexity, pages 260–274, 2004. [32] A. A. Razborov. Lower bounds for the size of circuits of bounded depth with basis {&,⊕}. Mathematicheskie Zametki, 41(4):598–607, 1987. English translation in Math. Notes. Acad. Sci. USSR 41(4):333–338, 1987. [33] A. A. Razborov. On the distributional complexity of disjointness. Theoretical Comput. Sci., 106:385–390, 1992. [34] A. A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya Math. (English version), 67(1):145–159, 2003. quant-ph/0204025. [35] A. A. Razborov and S. Rudich. Natural proofs. J. Comput. Sys. Sci., 55(1):24–35, 1997. [36] R. Santhanam. Circuit lower bounds for Merlin-Arthur classes. In Proc. ACM STOC, pages 275–283, 2007. 49 [37] A. Shamir. IP=PSPACE. J. ACM, 39(4):869–877, 1992. [38] R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proc. ACM STOC, pages 77–82, 1987. [39] S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–877, 1991. [40] L. Trevisan and S. Vadhan. Pseudorandomness and average-case complexity via uniform reductions. In Proc. IEEE Conference on Computational Complexity, pages 129–138, 2002. [41] N. V. Vinodchandran. A note on the circuit complexity of PP. ECCC TR04-056, 2004. [42] A. Wigderson. Information theoretic reasons for computational difficulty. In Proceedings of the International Congress of Mathematicians, pages 1537–1548, 1990. [43] C. B. Wilson. Relativized circuit complexity. J. Comput. Sys. Sci., 31(2):169–181, 1985. [44] A. C-C. Yao. Separating the polynomial-time hierarchy by oracles (preliminary version). In Proc. IEEE FOCS, pages 1–10, 1985. [45] A. C-C. Yao. How to generate and exchange secrets (extended abstract). In Proc. IEEE FOCS, pages 162–167, 1986. 50