A FOCS-related question

Actually, it’s not so much related to FOCS as to a specific paper in FOCS. I’m talking about the paper of Basu and Zell in which they formulate and prove an analogue over the real numbers of Toda’s theorem. I happen to know virtually nothing about real complexity theory, and even in standard complexity theory Toda’s theorem is pretty far from my usual interests of circuit complexity and derandomization, but their abstract nevertheless caught my attention for one single reason: the method of proof.

As far as I know, all of the proofs of (the classical) Toda’s theorem rely on heavy machinery from complexity and combinatorics, and tend to be quite involved. Basu and Zell’s paper also seems to be pretty long and technical, but their result is proved (and formulated) using tools from algebraic topology. For instance, the real analogue of #P is defined using the Poincare polynomial (the generating function of the Betti numbers, from a combinatorialist’s viewpoint). Basu and Zell are also kind enough to provide a definition of #P from a “geometric” viewpoint as well. My question is whether this topological or geometric intuition over GF_2 (or in classical complexity) can be extended to produce a new proof of Toda’s theorem.

By the way, if this post sounds like I don’t know what I’m talking about even more so than usual, that’s because I don’t know what I’m talking about even more so than usual. Apologies.

Although I’m not a topologist by any means, here’s what I think is happening in the proof of the main result: Basu and Zell relate the truth values of quantified formulas to various statements in semi-algebraic geometry; a little more specifically, quantifiers are projection maps and unquantified formulas are semi-algebraic sets. Then polynomial-time formulas reduce to nice questions about fibers of projections of semi-algebraic sets at a point, and these questions can be expressed in terms of Betti numbers. (As far as I know, this may well be a standard construction in real complexity; none of it seems to be all that deep.)

Basu and Zell’s main innovation seems to be to construct, from a semi-algebraic set S, a projection map \pi_Y,  and an integer p, another set D^p_Y(S) that has some nice computability properties and shares the first p Betti numbers with \pi_Y(S). Then with access to an oracle that helps us compute the Betti numbers, we can check the truth of a polynomial-time predicate with n quantifiers in polynomial time, which is essentially the statement of Toda’s theorem.

(By the way, it’s of course entirely possible and even likely that I’ve misunderstood some parts of the paper in the above outline. Corrections are encouraged — Basu and Zell’s outline of the proof is in Section 1.4.)

So can we use a similar argument to prove Toda’s theorem topologically, without going through the weird intermediate complexity class? Well, most of the steps outlined above seem to still go through if we’re working over \{0, 1\} instead of the reals, with two possible exceptions: the construction of the set D^p_Y(S), and the Betti numbers.

The construction of D^p_Y seems involved and technical, and I don’t have any intuition one way or the other about whether an analogous formula can be constructed in the classical scenario, so I’ll leave that be for now — if someone knows more, I’d love to hear from them.

The Betti numbers, however, are a more interesting obstruction. I may be entirely wrong, but as I understand it, describing nice (co)homology theories for algebraic varieties over finite fields is… difficult. Again, I have no intuition for what the appropriate analogue of the Poincare polynomial would be in the classical setting, but I suspect that it may be something not very elementary.


Tags: , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: