tea.mathoverflow.net - Discussion Feed (Bringing theoryCS over to mathoverflow)

peterwshor comments on "Bringing theoryCS over to mathoverflow" (7189)

2010-07-18T13:23:02-07:00

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

Not in my case, either. I think the best thing to do is try to make the TCS people as welcome as we can, and see whether they come. The cs tags listed by Steve Huntsman seem like a good idea (although I don't foresee much use for computer vision or neural computing).

Kevin Lin comments on "Bringing theoryCS over to mathoverflow" (6932)

2010-07-13T18:31:22-07:00

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! :)

Kevin Lin comments on "Bringing theoryCS over to mathoverflow" (6931)

2010-07-13T18:20:04-07:00

I like Steve Huntsman's suggestion. I think it's better to keep the cs. prefix --- hopefully there is a way to aggregate all cs.* posts on a single page?

aaronson comments on "Bringing theoryCS over to mathoverflow" (6921)

2010-07-13T15:15:48-07:00

> 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.

jbl comments on "Bringing theoryCS over to mathoverflow" (6908)

2010-07-13T06:27:06-07:00

(Although there are only 4 posts tagged cs.lg.learning, one of them is clearly inappropriately tagged, and this inappropriate usage has been much more common than the correct one so far.)

Suresh Venkat comments on "Bringing theoryCS over to mathoverflow" (6880)

2010-07-12T13:31:25-07:00

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

Steve Huntsman comments on "Bringing theoryCS over to mathoverflow" (6878)

2010-07-12T13:15:18-07:00

I propose adding the CS tags from areas on the arxiv (e.g., cs.CC.computational-complexity) and merging tags into these where appropriate. I know the arxiv isn't popular for Theory people but even so, consider the following subset of areas:

Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computer Science and Game Theory
Computer Vision and Pattern Recognition
Cryptography and Security
Data Structures and Algorithms
Discrete Mathematics
Formal Languages and Automata Theory
Information Theory
Mathematical Software
Neural and Evolutionary Computing
Numerical Analysis
Symbolic Computation

all of which (by my reckoning) could be construed as fair game on MO.

neelk comments on "Bringing theoryCS over to mathoverflow" (6865)

2010-07-12T05:45:00-07:00

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.

Kevin Lin comments on "Bringing theoryCS over to mathoverflow" (6863)

2010-07-12T03:21:06-07:00

If we don't already have enough qualified people, I don't imagine it would be difficult to recruit a few trustworthy and reputable TCS people for this via the many excellent TCS blogs out there...

Noah Snyder comments on "Bringing theoryCS over to mathoverflow" (6859)

2010-07-11T19:39:17-07:00

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!

Suresh Venkat comments on "Bringing theoryCS over to mathoverflow" (6857)

2010-07-11T18:56:59-07:00

I was thinking of something along the lines of what Kevin suggests. While this might seem on the surface to encourage balkanization, it might actually help initially, and once people start getting used to the site, they might be interested in other tags as well.

regarding the general math background of TCS folks, I think it's definitely a trend (Kelner is a good example) that students coming into TCS with strong math background are able to make significant contributions, because the nature of the hard questions in TCS have changed - needing more sophisticated math tools. So from one perspective, integrating TCS with MO is a good signalling mechanism for undergraduates in TCS that they should be paying attention to their math fundamentals. The only downside is that we lose outreach opportunities to the larger CS community that appears to be somewhat scared by MO :)

Annoyingly, there is no mechanism to communicate with committed participants on the area51 proposal - I would have ideally liked to have a larger discussion about this.

Kevin Lin comments on "Bringing theoryCS over to mathoverflow" (6856)

2010-07-11T18:38:09-07:00

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].

François G. Dorais comments on "Bringing theoryCS over to mathoverflow" (6855)

2010-07-11T18:10:05-07:00

So, at the risk of sounding pedantic, the only difference is that math folks tend to use punctuation and capitalization correctly. (This remark does not extend to spelling.)

Scott Morrison comments on "Bringing theoryCS over to mathoverflow" (6854)

2010-07-11T17:52:05-07:00

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.

Noah Snyder comments on "Bringing theoryCS over to mathoverflow" (6853)

2010-07-11T17:46:41-07:00

Here's a good example, my class at Harvard had two very strong undergrads who wrote undergrad theses on algebraic topology. 8 years later, one of them co-solved the Kervaire invariant problem (http://people.virginia.edu/~mah7cd/), while the other one is doing TCS (http://math.mit.edu/~kelner/).

Noah Snyder comments on "Bringing theoryCS over to mathoverflow" (6852)

2010-07-11T17:41:53-07:00

(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.)

Mariano comments on "Bringing theoryCS over to mathoverflow" (6851)

2010-07-11T16:55:54-07:00

Noah is quite right. The idea that most pure mathematicians even know what homological algebra is about is amusing :)

Suresh Venkat comments on "Bringing theoryCS over to mathoverflow" (6850)

2010-07-11T16:44:41-07:00

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.

Noah Snyder comments on "Bringing theoryCS over to mathoverflow" (6849)

2010-07-11T16:26:09-07:00

Also Harry, your list of "common topics" I don't think is actually as neutral as you think it is. For example you didn't list: Cantor-style set theory, logic, number theory, combinatorics, differential equations, functional analysis, Riemanian geometry, symplectic geometry, quantum mechanics, etc. Many of those are just as common and fundamental as topics that you did list, and several of them (namely the ones listed towards the beginning) are likely to be very well understood by TCS people. (The ones towards the end are more in a physics-y direction.)

You have a very particular view of what mathematics is (that you're likely to grow out of if you continue in math) which is not representative of mathematics and clouds your judgement of people in closely related fields.

Noah Snyder comments on "Bringing theoryCS over to mathoverflow" (6848)

2010-07-11T16:15:30-07:00

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).

Harry Gindi comments on "Bringing theoryCS over to mathoverflow" (6847)

2010-07-11T15:58:55-07:00

I'm a bit skeptical that TCS people learn the entire undergraduate math curriculum as well as the entire CS curriculum. I guess the TCS people here could correct me.

Kevin Lin comments on "Bringing theoryCS over to mathoverflow" (6846)

2010-07-11T15:53:14-07:00

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.

Harry Gindi comments on "Bringing theoryCS over to mathoverflow" (6845)

2010-07-11T15:14:08-07:00

I'm pretty sure that Joel and Francois were trained as mathematics undergrads and went to grad school for mathematics (which means that they had to take prelims in a lot of the areas I mentioned).

The difference is that TCS people go to grad school in a different department with different requirements.

Kevin Lin comments on "Bringing theoryCS over to mathoverflow" (6844)

2010-07-11T14:29:34-07:00

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.

Joseph O'Rourke comments on "Bringing theoryCS over to mathoverflow" (6842)

2010-07-11T12:23:13-07:00

@Harry: You are right about the differing backgrounds. So that presents both an obstacle, and an opportunity. I am rooting for overcoming the obstacle, but I am not sanguine that it will occur. But I wouldn't want my pessimism to dampen enthusiasm.

Harry Gindi comments on "Bringing theoryCS over to mathoverflow" (6837)

2010-07-11T09:07:51-07:00

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).

Joseph O'Rourke comments on "Bringing theoryCS over to mathoverflow" (6836)

2010-07-11T08:47:26-07:00

I am not sure I can justify this with cogent reasons, but my hunch is that although TCS would be welcomed at MO (by the MO community), the TCS people simply will not come when invited (however that is organized). It will feel too foreign to them. Setting up appropriate filtering takes knowledge and experience with MO, and I just don't see many having the patience to reach that point. My only idea to mitigate this hurdle would be a standard TCS filter, perhaps the very one Suresh has developed, available (somehow) via one-click. This would have the unfortunate consequence of insulating one community from the other, where the real gain would derive from more thorough mixing. I applaud your efforts, Suresh, but no path seems easy!

Noah Snyder comments on "Bringing theoryCS over to mathoverflow" (6820)

2010-07-10T14:49:35-07:00

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.

François G. Dorais comments on "Bringing theoryCS over to mathoverflow" (6816)

2010-07-10T13:28:17-07:00

Dear Suresh, my background is only cognate to TCS but you do have my full support as a moderator.

Kevin Lin comments on "Bringing theoryCS over to mathoverflow" (6815)

2010-07-10T13:26:51-07:00

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.

Suresh Venkat comments on "Bringing theoryCS over to mathoverflow" (6812)

2010-07-10T13:09:12-07:00

Regarding moderation, I guess my only concern is that it takes a while to earn enough reputation to do nontrivial moderation. For example, I can re-tag posts, but I can't yet edit posts. Since the subset of Q&A on which I can contribute is small, my reputation also grows slowly, so it takes longer to hit the desired levels. There are a few high-reputation theoryCS folks (David Eppstein is one, and Joe O'Rourke), but it takes a while to get up there.

Kevin Lin comments on "Bringing theoryCS over to mathoverflow" (6810)

2010-07-10T12:56:05-07:00

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.

Suresh Venkat comments on "Bringing theoryCS over to mathoverflow" (6807)

2010-07-10T12:18:58-07:00

@noah - that's what I imagined. But do you see the stated 'cons' as real ones, or not so real ?

Harry Gindi comments on "Bringing theoryCS over to mathoverflow" (6806)

2010-07-10T12:11:36-07:00

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

Suresh Venkat comments on "Bringing theoryCS over to mathoverflow" (6805)

2010-07-10T11:50:05-07:00

are you implying that MO might go the OSQA way as well ?

Noah Snyder comments on "Bringing theoryCS over to mathoverflow" (6804)

2010-07-10T11:49:44-07:00

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.

Harry Gindi comments on "Bringing theoryCS over to mathoverflow" (6803)

2010-07-10T11:09:39-07:00

Given the way people on meta.SO are responding to our requests, it seems like the second option would be best as soon as OSQA is (more) stable.

Suresh Venkat comments on "Bringing theoryCS over to mathoverflow" (6801)

2010-07-10T10:42:54-07:00

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) ?