Calling the questioner a troll after he has just accused his reasoned opposition of being “incapable of having a reasoned discussion about their field without getting defensive and clouding everything with personal insecurities” is most definitely the right thing to do.

]]>Here’s how it was explained to me. (I’m a theoretical CS guy, so I’m not speaking from personal experience.) In mathematics, especially pure mathematics, a result is “deep” if it exposes a connection between disparate fields of mathematics, where nobody expected a connection to exist. For example, the original proof of the prime number theorem is “deep” because it’s based on complex analysis. (It has little to do with the length of the proof.)

*In any case, who cares whether the “mathematics used are deep”?*

“Pure” mathematicians do. (Here, I use “pure mathematician” as a shorthand for “mathematicians whose work is not motivated by applications.”) They need a philosophy or aesthetic for deciding how important mathematical results are. Since “usefulness” is out, “depth” is a big one. (“Generality” and “elegance” are big ones too.)

]]>*isn’t the real problem with complexity theory that the resulting mathematics is usually superficial and shallow?*

and

*are complexity theorists ever saying something deep?*

and

*I don’t see why many people are incapable of having a reasoned discussion about their field without getting defensive and clouding everything with personal insecurities.*

**TROLL!**

at no point did I propose that “math is better than TCS” or that “subfield A of TCS is better than subfield B.” I don’t see why many people are incapable of having a reasoned discussion about their field without getting defensive and clouding everything with personal insecurities.

I think perhaps my real question should have been something like “is it the right time in history to solve the big problems of complexity theory?” in other words, is there anything to be gained from attacking the main questions head-on, as opposed to setting in for the long haul, developing a theory, and being perfectly happy with a lot of very incremental progress for the next 20 years. what should we expect of ourselves? should be people be encouraging their students to work in a different field?

as for the sweat-inducing prospects of applying topology to complexity theory:

– the stuff of freedman, et. al. is very cool, but the reason topology comes in there (topological quantum field theories) is very different (a priori, at least) from the reason it might be useful for e.g. circuit lower bounds.

– I think the hopes for topology in complexity theory revolve around connected-ness and information flow. for instance, we know there are problems for which every circuit of a certain type requires that there exist disjoint paths from every set of k inputs to every set of k outputs.

in other words, the problem itself imposes certain connectivity requirements on the circuit. this can be used to get very weak but non-trivial lower bounds on the number of wires required by any circuit that solves the problem (see valiant, pudlack, or raz and shpilka for examples of this that I can recall).

at this elementary level, one might hope that higher-order topological invariants (e.g. homotopy, homology) might lead to stronger lower bounds, but it’s unclear whether this is true, and what it should mean.

– bjorner, lovasz, yao, and others used topological methods to study size and depth lower bounds for algebraic decision trees. suppose you have a subset S of R^n and you want a decision tree that decides membership in S. one method to prove lower bounds is to count the number of connected components of S (or its complement). but if S is connected, then this only provides trivial bounds.

here, one can use higher order notions of “connectivity” like the betti numbers of S to get lower bounds on depth (this uses non-trivial results on the betti numbers of algebraic varieties, which I mentioned upthread somewhere).

I guess there is hope that similar methods might hold a lot of power, but I agree there is little evidence. there is some recent attempt by joel friedman to study this stuff more generally, but I don’t really understand what his paper is saying.

]]>*I’m* not sweaty over it. (Living in Canada, I’m not really sweaty over anything.)

Mike Freedman has had some interesting ideas about a topological approach to P vs. NP, but nothing concrete that I know of yet.

In a different direction, there’s also work by Freedman, Kitaev, and Wang (and more recently Aharonov, Jones, and Landau in STOC’06), which shows that simulating topological quantum field theories and approximating the Jones polynomial at a root of unity are BQP-complete.

As for P vs. NP, there’s no shortage of exotic ideas: the Mulmuley-Sohoni approach (based on geometric invariant theory), Mike Nielsen’s approach (based on geodesics in Riemannian manifolds), approaches based on cohomology, etc. etc. I don’t pretend to understand most of this stuff; what I keep coming back to is how any of it gets around the Razborov-Rudich barrier.

]]>