Write a note in SIGACT News advertising the site.
I was thinking (and maybe this is too pie-in-the-sky) that this post could be written jointly by the community, by editing this very post (I'll put a crude skeleton in place). The article, when published, could be attributed to the website "with contributions from" anyone who helped edit the post (but only real names, please).
I'd like to make a few requests though:
- Use an answer to discuss a particular aspect of the article. I understand that issues will overlap, but it's easier to track answers than have one giant comment thread below this question
- Make sure you use your real name when editing. We can use revision history to determine who changed what.
- I think it's also fair to assume that simple edits (syntax, spelling) are not at the contribution level that might merit "with contributions from", so try to focus on content edits, and we can all chip in to fix minor issues.
- If you want to discuss whether we should be doing this at all, a different question might be a better place for that. Frankly, I don't see a downside.
Current contributors (please update): Dave Clarke, David Eppstein, Kaveh Ghasemloo, Lev Reyzin, András Salamon, Peter Shor, Aaron Sterling, Suresh Venkatasubramanian.
Further Update: I think we should finalize all edits by Friday noon (Mountain time). At that point I'll take the text and links, convert to latex-ized PDF, and send it off to the SIGACT News Editor.
More updates. I'm now locking this post, since it's Friday @ Noon here in Utah. I'll start doing the latexing, and will link to a PDF shortly.
Questions Answered. In theory.
Questions Answered. In Theory.
Perhaps you're a computer scientist wondering how much the Axiom of Choice matters to the theorems you study and prove. Perhaps you're a mathematician who needs a top expert to explain what "randomness" really means in computability and complexity. Perhaps you need a list of problems that can be used to show polynomial-time hardness results, to strengthen your toolkit of reductions. Or perhaps you think a problem might be open -- but might just as easily be solved -- so you'd like to ask a group of professionals what they think.
cstheory.stackexchange.com provides this interaction "at the speed of the internet," by bringing together researchers from around the world, and across the broad spectrum of theoretical computer science. Active participants range from advanced undergraduates to well-established scientists. Currently the majority of participants are graduate students and postdoctoral fellows, but the number of senior researchers active within the site is growing quickly.
Even though cs.theory.stackexchange.com is only two months old, it can already boast of 2,000 registered users, 700 answered questions, and -- perhaps most exciting -- new research collaborations among computer scientists who otherwise might never have realized that they were working on related problems. The atmosphere of the site is a bit like a corridor discussion at a conference: researchers discuss and explain both folklore and the newest results, in a format that can be read at leisure.
Some questions and their answers are highly technical, but the answers from experts are often more than just answers; they contain insights that are not available in papers or textbooks. For example, a student who requested a "common sense" explanation for how padding arguments related to complexity class separations received an intuitive answer from Russell Impagliazzo; Scott Aaronson summarized the state-of-the-art in non-relativizing techniques; Jeff Erickson explained why the real RAM model is preferred in computational geometry; and a student who asked whether the Nisan-Wigderson pseudorandom number generator relativizes received an answer from Noam Nisan.
Questions have also generated new proofs: Peter Shor gave a reduction from Max-Cut with positive weights to a constant-factor approximation for the version of the problem with negative weights; Jukka Suomela demonstrated that DOMINATING SET remains NP-complete for planar bipartite graphs of maximum degree 3; Sariel Har-Peled showed that Hamiltonicity is NP-complete for k-regular graphs for any fixed k; and Per Vognsen outlined a proof for the Schwartz-Zippel Lemma using projective geometry.
In addition to specific technical questions, participants have asked for more general advice from the community, such as how to referee papers, possible Master's thesis topics in automata theory, pointers to recent purely functional data structures, suggestions for an inspirational talk about theoretical computer science, and how to find a job. The site is a place for the larger theory community to come together. The overall scope of the site is research-level theoretical computer science, broadly defined. Note that homework questions are not allowed on the site.
Everyone with a research interest in theoretical computer science is welcome to create an account. We encourage participation using real names -- and almost everybody does this -- but it's not required. Participation costs nothing, and takes as little or as much time as you choose.
Site Origin and Structure
Some of the founding members of cstheory.stackexchange.com participated in discussion of a proposed solution to the P/NP problem that spanned multiple blogs, led to the creation of wiki pages, and brought together researchers in disparate fields from around the world. This effort made it clear that the worldwide theoretical computer science community was ready for -- and needed -- a structured way to ask research-level questions and to consider answers to such questions. The success of MathOverflow.net (a site devoted to research-level mathematics) encouraged us to adopt the StackExchange software developed by Jeff Atwood and Joel Spolsky. This software provides a user reputation system built on up- and down-voting of contributions to highlight and encourage high quality, and to control spam. There is also a "Meta" area, for discussions about site scope and direction. Thus far, the system has worked extremely well and we are very pleased with it.
Who runs the site?
You do ! The site is moderated by the community, with users gaining access to more management tools as they gain more reputation within the site. We have an active core of users who diligently monitor the site, help improve the quality of questions and answers, and filter out spam. In fact, this very article is a product of community participation on the site.
But you don't have to worry about any of that to contribute to the numerous research discussions taking place right now. Please visit -- and participate in! -- cstheory.stackexchange.com, the 24/7/365 gathering-place for theoretical computer scientists from around the world to share information and insights.