Hi all
I know there's a thread on whether theoryCS is welcome on MO (answer: YES!, but I'd like to start a new thread on the potential logistics of actually doing this:

Some background:

as you all probably now, there's an area51 proposal (http://area51.stackexchange.com/proposals/8766/theoretical-computer-science) for theoryCS right now. It's in the commit stage, at the 34% level. New commits are slowing, and it's not entirely clear if we'll make the 100% cutoff under the current scoring system (MO reputation doesn't count :(). Among the many clones of SE is OSQA, a system that's been used to power a machine learning Q&A site (metaoptimize.com). The proprietor of that site, Joseph Turian, has expressed some interesting in setting up a clone for theoryCS as well, using that software.

So right now we are faced with three options:
* wait on area51 and hope that we get enough commits to cross over into beta. Pros: we get the SE 2.0 infrastructure and maintainence - cons: we might never get there, and we're dependent on SE to decide whether we are sustainable or not.
* shift over to OSQA with the help of Joseph: pros: we can be up and running soon. cons: it's not necessarily as permanent as SE, and things like jsmath support are not currently baked in (although we might be able to borrow your hacks)

Of course the third option is the most relevant one to MO: namely

* merely encourage all theoryCS folks to come and invade MO :).

The pros are fairly clear: a friendly and overlapping community, built in support for latex rendering etc (OSQA doesn't have this yet).
The cons are (from my discussions with people):
* getting "lost" inside MO, because of the vast amount of discussion unrelated to theoryCS (I have a long list of ignored tags, but I still have to wade through lots of questions to get to relevant things)
* will moderation work as well: I recognize that one of the reasons for the success of MO is the excellent and carefully thought out moderation. For the theoryCS component to work as well, we'd need the same treatment, and a lot of this is domain specific - "is this question a homework question", "is this within the scope of theoryCS even if it's not a pure-math question" and so on.
* cost issues: this is being funded out of a MATH professor's grant. Now I'm sure we can get financial support from the theoryCS side if needed, but do we ? and how much is it etc

I'd like to know how MO folks feel about these matters. Firstly, do you think that the stated cons are real cons ? If yes, would you be interested in working with theoryCS folks on solutions (this last question sounds aggressive, but it's not: I fully respect that MO is a smoothly humming machine right now (from my perspective) and I'd understand a reluctance to tinker too much with it) ?

I think we'd certainly be thrilled to have TCS questions at the level of the ones in that proposal. We already have some CS experts hanging around (mostly in quantum computation). I think it'd be good for math and TCS not to get too balkanized.

If SO doesn't meet our demands, it seems like we'll probably move to OSQA whenever it's stable.

Personally, I'd like to say: Welcome! Make yourselves at home! Feel free to invade!

I think that TCS and "mainstream(?) math" have a lot to learn from one another and would benefit from more interaction, and MO would serve as a good venue for this.

As for your cons:

• getting lost -- This is why we have "interesting tags" and "ignored tags", as well as RSS feeds for each tag.

• moderation -- As TCS activity increases on MO, there will be more qualified TCS experts around to better moderate TCS questions, so this issue will quickly go away, if it's even much of an issue at all.

• cost -- I don't know for sure, but I don't think this is a big deal. I don't think that TCS will significantly increase the traffic to MO, and hence it won't increase hosting costs by that much, either.

Despite the current dearth of real TCS experts around, I think there are enough high-reputation/active members who are at least reasonably knowledgeable about TCS -- knowledgeable enough to tell whether something is a homework question or not, at least.

Greg Kuperberg is another high rep user with TCS knowledge. I wouldn't be too worried about moderation issues.

The getting lost to me is the biggest issue, but that's an issue for TCS people to decide, I'm not sure what if anything we can do about it.

Do the TCS people see themselves as members of a different community? What background do other pure mathematicians share with them?

I mean, it's safe to say that most pure mathematicians have at least a basic understanding of (or at least learned at some point) real analysis, differential geometry, point-set topology, linear algebra, modern algebra (groups, rings, modules), commutative algebra, homological algebra, algebraic topology concerning the fundamental group, etc.

I'm pretty sure that even the most specialized people here (I would have to say that the set theorists here seem to fit that bill) have a basic understanding of most of the above.

TCScientists don't seem to (in general) share that background (correct me if I'm wrong), and for that reason, would rather not have to wade through all of that. It seems like although TCS is part of mathematics as a discipline, it's not the case that TCScientists are part of the mathematical community by default (not to say that there aren't members of both).

The same disparity in background seems to hold for logicians as well, to some extent.

But flipping it around, "mainstream" mathematicians in general don't seem to know too much about logic, nor theoretical computer science, either.

Logicians seem to have been doing just fine on MO (take a look at who the highest reputation user is); I don't see why theoretical computer scientists would have any problems, either.

Like I said earlier, and like Joseph says above, it's a good opportunity for these different fields to learn from one another.

Most of the theoretical computer scientists that I know and that I can think of are sufficiently qualified in most of the "prelim" material that you list, at least in my opinion.

Grad students learn material way faster than undergrads do. Hence, someone who has a Ph.D. and has done math-y sorts of TCS should have more math background than many math majors. Also, plenty of CS grad students were math majors (most of the CS Ph.D.'s I know were math majors, of course that's unsurprising given that I'm more likely to know people who were math majors).

obviously I can't speak for tcs folks in general, but based on my interactions and the background I've had to acquire myself outside of undergrad/grad school, most tcs folks are only "intuitively" familar (i.e not at the level of citing/proving actual results) with most of topology, analysis and differential geometry. Our algebra skills are fairly strong, but still only at the concrete level (possibly not at the level of modules etc). Now this varies: the computational topology folks know their homology and cohomology inside out, the metric embedding folks are very strong in functional analysis, and so on. But it's piecemeal and as-needed, as opposed to being a common base. and that's the problem.

so we speak the same language of mathematics, but focus on very different core topics.

(Indeed, I wasn't sure whether it was a good or bad idea to out myself as someone who can't really do any serious homological algebra.)

Just to echo Kevin on the "cost" con: don't worry about this at all. While we might have uncertainties regarding SE 2.0 (and OSQA or something else as a fallback), however it pans out we expect funding to be a relatively minor hurdle.

I noticed that Scott Aaronson and Peter Shor recently posted questions. Was this somehow prompted by Suresh, or by this meta thread?

I think that the issue of TCS being "drowned out" by the rest of the site can be allayed by setting up a "sub-site" for TCS, achieved by simply giving all TCS questions a specific tag, maybe [cs-theory] or something. If you're only interested in TCS questions/answers, then you can just go to the "sub-site" http://mathoverflow.net/questions/tagged/cs-theory rather than the main page http://mathoverflow.net. If you have a question about something that isn't directly related to TCS, but you still specifically want theoretical computer scientists to see your question, then you can also tag your question with [cs-theory].

I agree with Kevin that having a good tag for TCS questions is a good idea. The key is making sure there are a few people who know TCS and check the site often enough and have enough rep to tag making sure that everything that should get tagged does. Those people need to *not* be filtering out other things!

The only downside is that we lose outreach opportunities to the larger CS community that appears to be somewhat scared by MO :)

You may gain some outreach opportunities as well: a lot of Theory A (what in the US is just called "theory") is not well known to Theory B people (ie, "semantics" or "verification"), and vice-versa. Partly, it's because the mathematical tools we most commonly use are quite different. Building on your example of what algebra computer scientists know, from my POV modules are so concrete I have trouble imagining what they could be used for! (Offhand, I imagine they might appear in the theory of regular expressions, perhaps to explain the connection between Kleene algebras and finite automata.)

However, there are a lot of pure mathematicians living in between between these two poles, and perhaps they could help us talk to each other.

note that it.information-theory already exists. as does cs.lg.learning-theory. It might be better to drop the cs. prefix as redundant, and then (for example) the tag complexity-theory could potentially be merged into cc.computational-complexity or something like that

> I noticed that Scott Aaronson and Peter Shor recently posted questions. Was this somehow prompted by Suresh, or by this meta thread?

At least in my case, not at all -- it was prompted by having a question that I wanted people to look at! :)

To amplify something Suresh said, it seems to me that math and TCS have drawn noticeably closer within the last 15 years, as TCS got much of its "internal housekeeping" in order and became emboldened to tackle new types of questions. Today there are great mathematicians like Timothy Gowers, Terry Tao, and Jean Bourgain thinking about TCS-inspired questions, and TCSers like Avi Wigderson using recent and high-powered math tools (and others, like Ketan Mulmuley, attempting to use even higher-powered ones...). Sure there are differences in background and culture, but one of the main ones I observe---namely, that TCSers tend to be more interested in concrete problems than general theories---is arguably not *such* a disadvantage on MO! Basically, I think greater TCS involvement in MO would reinforce an existing positive trend for both fields.

Sure there are differences in background and culture, but one of the main ones I observe---namely, that TCSers tend to be more interested in concrete problems than general theories---is arguably not such a disadvantage on MO!

Actually, I don't see how this is a disadvantage in any way at all! :)