Posts Tagged ‘toda’s theorem’

A FOCS-related question

July 27, 2009

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.