I think Klauck’s lower bound can also be generalized as you describe, but I’d have to check. I would conjecture that the truth is simply n — my only evidence being that, in the past, it’s often been possible to get rid of log factors in communication protocols.

I showed your O(sqrt(n)logn)-bit AM-communication protocol for the inner product function today at Tsinghua. It went nicely. I think it’s a nice result, and a simple and cool example for how polynomials can help “spread” an error.

By the way, I’m sure you know it but it might be worth noting that (if I’m not wrong), your protocol generalizes such that for any two numbers b,m such that b*m>=Omega(nlog^2n), Merlin can send m bits to Alice, and Bob can send b bits to Alice, such that Alice can compute the inner product or to prove Merlin false (whp).

By the way, does Klauck’s result prove an Omega(n) lower bound on the value of b*m ? What do you tihnk the truth is: n or nlog^2n (or, most likely in my eyes, nlogn)?

When one sees a relativization statement including the expression “A^B”, is A to be interpreted as a set of languages or as a class of machines?

Having said that, there’s a natural oracle access model under which L=SL not only algebrizes but also relativizes. The model is the following: an L^A machine gets a polynomially-long, write-only oracle tape; and whenever it gets an answer, the oracle tape is reset to 0. An SL^A machine gets the same, and also is not allowed to make nondeterministic transitions while the oracle tape is being written to. Under this model, the problem just boils down to searching an undirected graph in logspace, but where you can use the oracle to tell you what the neighbors of a given vertex are. It’s clear that Reingold’s proof carries through to this case with no changes.

It’s an interesting question what happens if the SL^A machine is allowed to make nondeterministic transitions while the oracle tape is being written to.

Sorry your interesting message got held up in my spam queue!

Yes, Russ Impagliazzo and Lance himself both pointed me to that section of Lance’s survey paper. Avi and I will be sure to credit Lance with having the basic idea of a low-degree oracle — even though (1) he didn’t adopt the asymmetric definition that seems necessary for making statements about all oracles rather than just some of them, and (2) he didn’t seem to be interested in algebraic oracle separations, which are our main results. (We’ll also, of course, credit you with asking the question that led directly to our work! )

As for the asymmetry in oracle access, the “conceptual” reasons to go this way are

(1) It’s clear that C^A ⊆ D^A implies C^A ⊆ D^~A, but it’s not clear that it implies C^~A ⊆ D^~A.

(2) What we’re trying to model is starting from a Boolean circuit C (possibly involving oracle gates), and then reinterpreting C as an arithmetic circuit over a larger field or ring. If C can already query the low-degree extension, then it might do so in non-arithmetic ways (i.e., it might access individual bits in the binary representation of ~A(x) for various x’s). And in that case, we’d have to take a low-degree extension of a Boolean function derived from the original low-degree extension, and so on ad infinitum. Indeed, that’s essentially what Lance does, and is the reason why his definition is more complicated than ours. The more complicated definition models a sort of “recursive arithmetization,” which is possible in principle but which isn’t used in any existing result that I’m aware of. My results with Avi don’t say anything about the limits of this recursive arithmetization; it would be extremely interesting if one could do so.

You raise a good point about composition. What one can say is the following: if C^A ⊆ D^~A and D^A ⊆ E^~A for all A,~A, then C^A ⊆ E^~~A, where ~~A denotes the “double algebrization” of A as above. However, I can’t think of a single instance in our paper where we actually need this fact (i.e., where we have to compose two algebrizing inclusions, neither of which is also relativizing).

Lastly: I completely agree that one of the most useful applications of this work is to indicate which open problems might still be resolved with algebrizing techniques! Here’s one of my favorite examples: is PH ⊆ PP?

Not that I can see, although Peter Sarnak asked the same question when I gave the talk at IAS…

Good to see that your idea has gained so much heft since you told me about it. I do think this is the “right” approach to formalizing the distinction between what we’re capable of proving at present, and what we’d like to prove.

One aspect of the definition that might cause some issues is the asymmetry between Boolean oracle access and algebraic oracle access. For instance, is it true that if A in B and B in C algebrize, then so does A in C? The fact that relativization composes is very convenient.

Is there some conceptual reason why you went with this definition rather than the one where both sides get access to the algebraic oracle? Or is it simply that the analogues of your results in the alternative model seem harder to prove?

Not sure if you know this, but Lance Fortnow defined a very similar model in his paper “The Role of Relativization in Complexity Theory”. He defines a notion of “algebraic extension” and shows (Theorem 5.6) that IP = PSPACE relative to the algebraic extension of any Boolean oracle. I wonder how that result relates to the question in your paper of whether IP =PSPACE algebrizes when both sides are given access to the algebraic oracle.

There are advantages to your asymmetric definition - Madhu’s question is a very nice one. In general, it might be interesting to study how “structurally complex” A can get as a function of B so that NP^A in P^B still holds for some B. But the most useful thing about your work, for me, is the (implicit) identification of a “grey zone” where we still have a chance with the old techniques…