19
$\begingroup$

Hi all,

I chatted with Lance Fortnow at FOCS about the various ideas I brought up in my answer to "Beta period progress". This "question" is about the first, namely:

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:

  1. 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
  2. Make sure you use your real name when editing. We can use revision history to determine who changed what.
  3. 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.
  4. 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.

PDF Update: Here's a link to the PDF, with the citation format taken from this meta discussion. I have emailed this version to Brendan Mumey (SIGACT News editor)

Questions Answered. In theory.

cstheory.stackexchange.com

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.

Visit cstheory.stackexchange.com

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.

$\endgroup$
54
  • 4
    $\begingroup$ I like the point about capturing insights not present in books or papers. $\endgroup$
    – Suresh Venkat
    Oct 28, 2010 at 21:32
  • 2
    $\begingroup$ I'm open to removing it. I've found that it's a source of puzzlement to people not familiar with the MO model, and it does help explain how spam gets removed. $\endgroup$
    – Suresh Venkat
    Oct 29, 2010 at 2:13
  • 2
    $\begingroup$ Another possibility is to modify that part to become an answer to a problem, e.g. who runs/manages the site? the community! What is the system used for keeping the discussions sane and high quality? the reputation system! and it works this way ... and it is just there to take care of abusers, it is not a big deal, you don't need worry about it after posting your first question/answer. $\endgroup$
    – Kaveh
    Oct 29, 2010 at 5:44
  • 3
    $\begingroup$ Suggestion: Once it's written, in addition to submitting it to SIGACT News, perhaps it could be guestblogged as well (someplace other than/in addition to the GeomBlog, as I am assuming people who follow the GeomBlog are aware of this site), much as Bill Gasarch posts his book review columns. $\endgroup$
    – Aaron Sterling
    Oct 29, 2010 at 13:42
  • 1
    $\begingroup$ I changed the opening structure a fair amount, toward something I thought would better capture and maintain the reader's interest. I'll try to get to the second half tomorrow, unless people decide they prefer the structure to be the way it was before. $\endgroup$
    – Aaron Sterling
    Oct 30, 2010 at 18:30
  • 1
    $\begingroup$ @Aaron: My main criticism is that you deleted much of the success stories suggested by Peter Shor, without providing adequate replacement text. I see that it is implicit in the introductory paragraph, but having more explicit success stories would be, in my opinion, better. $\endgroup$
    – Dave Clarke
    Oct 30, 2010 at 19:21
  • 2
    $\begingroup$ is there possibly too much information about SE ? $\endgroup$
    – Suresh Venkat
    Oct 31, 2010 at 6:34
  • 4
    $\begingroup$ I also wonder if we need a self-referential throw in of the form "This very article you're reading was written by the community on the site" $\endgroup$
    – Suresh Venkat
    Nov 1, 2010 at 6:46
  • 2
    $\begingroup$ We could say "Some of the answers contain new proofs which were discovered in response to the question" There are at two of these I'm aware of, and probably a bunch more. cstheory.stackexchange.com/questions/2505/… and cstheory.stackexchange.com/questions/2312/… $\endgroup$
    – Peter Shor
    Nov 1, 2010 at 21:31
  • 3
    $\begingroup$ @Peter: I also like Vognsen's "new" proof of the Schwartz-Zippel lemma here: cstheory.stackexchange.com/questions/1772/… $\endgroup$
    – arnab
    Nov 2, 2010 at 0:00
  • 2
    $\begingroup$ I like this version, and it seems to be approaching a fixed point. Any more success stories that should be included? $\endgroup$
    – András Salamon
    Nov 4, 2010 at 10:07
  • 2
    $\begingroup$ I really like John Watrous' answer to the gcd problem, and propose that this be a top-level replacement for the note on listing poly-time hardness results ? cstheory.stackexchange.com/questions/2708/… $\endgroup$
    – Suresh Venkat
    Nov 4, 2010 at 16:00
  • 3
    $\begingroup$ @Peter: Agree with your comments; the GCD question is a nice addition. I would be happy to see the current version (revision 40) as the basis text for Suresh to edit. $\endgroup$
    – András Salamon
    Nov 4, 2010 at 17:01
  • 2
    $\begingroup$ Some citations reference discussions rather than questions or answers. For those citations, it didn't seem to make sense to single out the questioner or any particular answer (as was discussed on the meta link). Basically there are three kinds of citations: interesting questions, interesting answers, and interesting discussions. For the first two, I use names. $\endgroup$
    – Suresh Venkat
    Nov 5, 2010 at 23:45
  • 2
    $\begingroup$ @Suresh. Good work. Thanks for initiating this and pulling all together in the end. (spanned multiple blogs sounds okay to me.) $\endgroup$
    – Dave Clarke
    Nov 6, 2010 at 13:17

7 Answers 7

Reset to default
10
$\begingroup$

Two suggestions:

  1. Noam's post can be useful, specially in addressing the issue that the site does not worth the time it is going to take from seniors.
  2. I think we should also mention that the site is creating (or bringing back) a sense of bigger tcs community, which, if I remember correctly, is something that Lance has written about a number of times, e.g. when he was arguing for larger conferences.
$\endgroup$
1
  • 7
    $\begingroup$ I agree, especially with point 2. While I do not think of myself as completely belonging to "mainstream tcs" (or even as working solely in theory), I definitely thinking of myself as a mainstream user of this site. $\endgroup$
    – Lev Reyzin Mod
    Oct 28, 2010 at 20:09
5
$\begingroup$

From Lev's comments, we need more suggestions for examples of success stories.

  • open problems being resolved
  • researchers connecting in a way that would be difficult otherwise (the Kintali/Stolee example)
  • simple questions revealing open problems
  • motivation for new (graduate) students coming into theory
  • New connections with application areas for TCS

Any other success stories. If you have a good success story, and you're too busy to write a few sentences about it that fit well into the article, you should post this success story in an answer and somebody else could incorporate it.

$\endgroup$
4
$\begingroup$

Participation costs nothing but time.

I think this is a bad sentence. I have already mentioned it in my first answer, but let me repeat it: time is very important, specially for senior researchers, and it is more important than money. I have talked with a number of senior members of our group and have tried to convince them to use the site, one part of their reply has been: we have our own (hard) questions, we prefer to use our time to work on our own questions.

We need to say that it is not going to be a large time sink with little benefits. We have demonstrated this in the article, but that sentence is in the reverse direction.

How about adding something like: as many researchers have found, it worths the time spent on the site by saving you the time spent on small obstacles in your research. it helps you and community to research faster. (and probably this is the main reason for the site)

$\endgroup$
2
  • $\begingroup$ See my modification. $\endgroup$
    – Suresh Venkat
    Nov 4, 2010 at 14:34
  • $\begingroup$ @Suresh: it seems good. $\endgroup$
    – Kaveh
    Nov 5, 2010 at 0:00
3
$\begingroup$

How long should this article be?

If we can answer this question, then it will be easier to know how much text to put into each section to keep the article balanced.

The current revision (rev 9) is 671 words. Do we want more or less? 1000? 2000?

$\endgroup$
4
  • 1
    $\begingroup$ I'd think that getting a good article in SIGACT News is much more important than how long it is (although I don't think it should be more than two pages or so). $\endgroup$
    – Peter Shor
    Oct 31, 2010 at 14:39
  • $\begingroup$ My point is merely that it'd be easier to structure/balance if we know what the page limits are. $\endgroup$
    – Dave Clarke
    Oct 31, 2010 at 14:48
  • $\begingroup$ I don't think there are explicit page limits. Peter's idea of 2 pages or three is reasonable. The SIGACT font is large, so 3 pages doesn't go that far. I'd say for now that we should ignore length limitations (within reason) $\endgroup$
    – Suresh Venkat
    Nov 1, 2010 at 6:41
  • $\begingroup$ I should also add (and I want to work on this) is that we can definitely expand the middle some more, with concrete use-cases to explain the different ways in which the site can work for us. $\endgroup$
    – Suresh Venkat
    Nov 1, 2010 at 15:07
3
$\begingroup$

Does anyone know - what is the deadline for this article to make it into the next issue? And are we allowed to embed links into the final article (this magazine seems to come out in print...)?

$\endgroup$
5
  • $\begingroup$ I just looked. 1 November! Embedded links seem not to make too much sense. Or in any case, we shouldn't relay on them. Perhaps some ugly footnotes or bib. $\endgroup$
    – Dave Clarke
    Nov 1, 2010 at 15:35
  • $\begingroup$ Deadline thereafter is 1 February. $\endgroup$
    – Dave Clarke
    Nov 1, 2010 at 15:43
  • 3
    $\begingroup$ If we submit soon, perhaps they can give us some leeway w/ Nov 1? It would be really nice to get this out earlier than later. $\endgroup$
    – Lev Reyzin Mod
    Nov 1, 2010 at 15:52
  • $\begingroup$ I already talked to Brendan Mumey and he can give us a few days. But I think stretching it beyond this friday is a bad idea. $\endgroup$
    – Suresh Venkat
    Nov 1, 2010 at 22:38
  • 2
    $\begingroup$ I will also volunteer to convert the text into latex with footnotes/bibs once we stabilize (no sense doing it right now). $\endgroup$
    – Suresh Venkat
    Nov 1, 2010 at 22:39
2
$\begingroup$

I really like both the rhythm and the examples of the first paragraph, but think it should be changed a little, I'm just not entirely sure how. I've tried to be as constructive as I can, given that I don't have a concrete idea on how to change it.

It currently (Rev 10) reads:

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.

I have comments on each of the four examples in this opening paragraph:

(1) I'd guess that most computer scientists have not wondered how the Axiom of Choice matters to CS; most probably just think that it doesn't. The fact that we got a really interesting answer to the contrary is a success story for the site. One of the things I enjoy most about the site is that I have learned interesting answers to questions I never would have thought to ask, not because they are not in my area, but because I always assumed the answer was trivial or never had occasion to think about them.

(2) Are there any non-CS-mathematicians who read SIGACT News? (Indeed, even the OP for that question is chair of his CS department, in addition to a joint appointment in the Math Dept.) Laurent Beinvenu's answer to that question was great, but I think we need to rephrase how we're selling it in this opening paragraph. I'm not sure the following is a good way, but I'll just note that his answer is like a short tutorial/primer on ML-randomness (basically all it lacks is the most recent results), something which might appear in a publication like SIGACT News.

Note that the amount of effort to write such a thing for such a publication is much greater than on this site, and would take several months to go through the publication pipeline, if it happened at all. Here we got a direct line to the source, and we got just the part of the tutorial we wanted, right away.

(3) A list of problems that can be used to show polynomial-time hardness results seems like a great resource for graduate students and people entering that area of research fresh, but I imagine experts in that area are familiar enough with the literature to have produced much of the entire list on their own. I think it's important that the paragraph clearly recognizes the correct audience for such a question, as is already done in the first two examples.

Again, maybe (but I'm not sure) a good way to think about it is that such a list is like part of a short tutorial that might appear in a publication like SIGACT News, but with a much lower barrier to creation (but still high quality).

(4) The last example is great. It's universal: it applies to graduate students and experts, everyone has had an experience where they wished they could do exactly this. And on this site, you can. It's a great pre-punch-line for this paragraph (the punchline, of course, being "Visit tcs.se" on the next line).

$\endgroup$
2
  • 2
    $\begingroup$ (2) Even if there aren't any non-CS-mathematicians who read SIGACT news, that doesn't mean we need to change the wording of that section. However, it might be good to rephrase this to somehow indicate that these types of questions can get a great answer. This might also be incorporated into the next section (Visit ...) $\endgroup$
    – Peter Shor
    Oct 31, 2010 at 17:23
  • $\begingroup$ Would rewriting the third sentence as "Perhaps for your research you need a list of problems that ..." address your concerns here? I can't decide whether it's an improvement or not. $\endgroup$
    – Peter Shor
    Nov 4, 2010 at 1:42
1
$\begingroup$

Are there any citations already in the literature that we can point to as success stories? When I search Google scholar for mathoverflow I find 67 hits but nothing under cstheory.stackexchange.com — I'm not sure whether that means that it's so new that it hasn't had a chance to develop citations or that I'm just not trying the correct search terms.

$\endgroup$
1
  • 4
    $\begingroup$ I don't know if any papers have actually cited cstheory yet: it might be too soon. even on MO it took a while for the first citation to emerge, if I recall right. $\endgroup$
    – Suresh Venkat
    Nov 4, 2010 at 7:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .