Question: Algorithm to sort pairs of numbers.

I believe that this question is at the level of midterm/final exams in an algorithm course and not at the level of research. Given the positive comment from one of the moderators and the high score (both of which are unbelievable to me), I do not mind if people keep it open, but I will not claim that this website is for research-level questions anymore, and I recommend others to stop doing so, too. The “research-level questions” restriction has not been enforced consistently anyway, so we should be just honest.

  • 2
    $\begingroup$ @Tsuyoshi: Thanks for bringing up the discussion. Do you have other examples like this one? I'm wondering if this is a special case, and it may only happen once for a while. $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 16 '11 at 16:01
  • $\begingroup$ @Hsien-Chih: I do not have any other examples right now. $\endgroup$ – Tsuyoshi Ito Mar 16 '11 at 16:17
  • 5
    $\begingroup$ As a OP of problematic question I just want to say that I didn't know what kind of questions are usually asked on cstheory. I stated the problem on SO first, but I didn't find satisfactory answer so I tried my chances here. After looking at other question I agree that question isn't on the level of this site. I hope that next time I will have a question better suited for this site :) $\endgroup$ – Klark Mar 16 '11 at 16:22
  • 14
    $\begingroup$ As the moderator who commented on the question: Firstly, I found the question interesting, so I commented. It's called encouragement. Secondly, I do not work in algorithms, so it is difficult for me to always determine the level of the question. Thirdly, it seems impossible to please you: close a question and you complain, comment on a question and you complain. $\endgroup$ – Dave Clarke Mar 16 '11 at 16:41
  • 24
    $\begingroup$ I have been arguing that we should exclude (a) typical homework questions for undergrad courses and (b) questions the answer to which is easily findable on wikipedia, or using Google. On the one hand, if we start answering questions of type (a) and (b), I think we'll rapidly degenerate into a site that will lose many of our current participants who want research-level questions. On the other hand, I'd like to still answer relatively elementary questions for practitioners who could use an answer. $\endgroup$ – Peter Shor Mar 16 '11 at 19:50
  • 3
    $\begingroup$ I think Tsuyoshi Ito is right. Since we have a lot of people in complexity, questions from that area are judged very harshly; things I have not seen in my Master course are declared too basic. In other areas, stuff I have seen in my Bachelor course is accepted. This is nothing new. $\endgroup$ – Raphael Mar 16 '11 at 21:06
  • 6
    $\begingroup$ @DaveClarke: My personal view is that this question shouldn't have been encouraged, because even if it was non-obvious, it's not research level. $\endgroup$ – Suresh Venkat Mar 16 '11 at 22:30
  • 11
    $\begingroup$ I think the question is fine and there is no need to change the scope. $\endgroup$ – Jukka Suomela Mar 17 '11 at 13:06
  • 2
    $\begingroup$ Doesn't CStheory allow certain other questions that are clearly "non-research-level," such as whether or not a problem is NP-hard? Maybe there is a different phrase that needs to be used for describing what kinds of problems are not allowed...for example, maybe saying that a question has to be "non-trivial or otherwise interesting to a researcher" would be a better criterion. I think Tsuyoshi is right that we've already diverged from "the sort of problems that two professors might discuss"...why not define it as "the sort of question that a professor would find interesting?" ...(contd.) $\endgroup$ – Philip White Mar 17 '11 at 15:30
  • 2
    $\begingroup$ ...(contd.) This criterion ("what a professor/researcher would find interesting") is relatively subjective. As such, it may be a little tricky to enforce, but might be more in line with what you're really going for...you don't to bore or drive away professional researchers. $\endgroup$ – Philip White Mar 17 '11 at 15:31
  • 8
    $\begingroup$ (1) IMO, one of the benefits of the site is that a researcher in field X can ask a question that is easy for a researcher in field Y. The difficulty of a question varies a lot by background too, not only by experience. (2) For this particular question, I think the OP would get quick and good answers on forums.topcoder.com where this kind of questions are encouraged; so, I would slightly prefer redirecting the OP, although I don't feel adverse to keeping the question. (3) @Philip: IMHO "Is X NP-hard?" is or is not a research question depending on X. $\endgroup$ – Radu GRIGore Mar 17 '11 at 19:04
  • 1
    $\begingroup$ Due to traffic volume mathoverflow can afford to discriminate "non-research level" question to math.stackexchange. There doesn't seem to be much noise here. Besides, where are database theory people? $\endgroup$ – Tegiri Nenashi Mar 22 '11 at 21:41
  • $\begingroup$ I don't think traffic is the main point for us, if traffic was the main objective we could have stayed on MO. We tolerate non-research questions to some extent but that is not the definition of our scope. Having a few interesting non-research question is OK, having too many is bad. If we remove the requirement of being research level from our scope then it seems to me that it would be difficult stopping lots of them being posted, we already get many off-topic question even thought the FAQ says that this is a research level site. On the other hand, a researcher might ask an interesting $\endgroup$ – Kaveh Mar 25 '11 at 21:32
  • $\begingroup$ non-research level question from another researcher from time to time (but not many), and that is OK and fits in the scope of our site (but I don't think we need to state it explicitly because stating this explicitly will cause more trouble than it will solve). Anyway, I think we have had enough discussions about scope recently and my personal opinion is that we should stick to the last decision at least for sometime (say a year) before revisiting it. $\endgroup$ – Kaveh Mar 25 '11 at 21:34
  • $\begingroup$ In reality our criterion is "of interest to researchers" instead of "research-level". However, a non-researcher would have a hard time telling what interests researchers, so probably "research-level" is a better, though less accurate, descriptor. $\endgroup$ – Lev Reyzin Mar 26 '11 at 4:21

Well, should I say: No, not yet another discussion on the scope?! :) We have discussed this already several times and I think we have reached a decision. I should say that I don't like discussing the same topics again and again in short periods.

If a policy is not enforced we should discuss why it is not being enforced, and not directly go to changing the policy.

Tsuyoshi, if you think a question is off-topic because it is not research level then vote to close the question and comment your opinion so others will also do the same thing. If there is a disagreement start a discussion on meta. Remember, the site is run by the community not just moderators. Among several hundreds of users on he site there will be some who will up-vote non-research level questions because they are interested in the answer. I try to close the questions that it seems clearly off-topic, but when it is not I prefer high rep users like you to close the question. It teaches other users how and when to close a question, and then we need less mod intervention. (as you know we cannot cast regular votes, and based on the experience I had, commenting that stating that I am voting virtually doesn't seem to have much effect.)

I don't know if other share it but my feeling is that recently the number of question closed without mod intervention has dropped significantly and that is not good.

  • $\begingroup$ The point is that I agree to Dave that the question is interesting and I do not want to vote to close it. $\endgroup$ – Tsuyoshi Ito Mar 17 '11 at 10:52
  • 7
    $\begingroup$ @ Tsuyoshi Ito, then you are also part of the problem! (and shouldn't have blamed Dave for his interest ;). I don't think that the rules need to be enforced as strictly as you think, if there are not 5 high rep users who want to vote to close the question then that is it. (I personally think that tolerating and leaving some non-research level questions which are of interest to enough researchers as open is OK, the reasons we had for making the site research-level probably does not apply to non-research question which are interesting to researchers. (more) $\endgroup$ – Kaveh Mar 17 '11 at 10:59
  • 5
    $\begingroup$ But I would argue against changing the scope from research-level. IMHO, as we have made an exception to reasonable number of applications-of-theory questions, we can make a similar exception for researchable number of very interesting non-research level questions.) $\endgroup$ – Kaveh Mar 17 '11 at 11:03
  • $\begingroup$ Tsuyoshi, if you don't want to vote to close it, what are you complaining about ? I really don't get it. $\endgroup$ – Suresh Venkat Mar 17 '11 at 22:04
  • 2
    $\begingroup$ @Suresh: This is my point. $\endgroup$ – Dave Clarke Mar 18 '11 at 7:41
  • $\begingroup$ @Suresh, based on previous meta-discussions, I think @Tsuyoshi's problem was that he wants us (especially himself) to follow the policies (which is the right thing to do but IMHO we don't need to be too strict) but thought that the question is reasonable and shouldn't be closed, therefore his point that "we should stop ..." (but I think it could be put in a little bit nicer way :) ). $\endgroup$ – Kaveh Mar 25 '11 at 21:26
  • $\begingroup$ well I think that the 'research level' designation is always going to be somewhat of a moving target. Expecting strong consistency, and throwing out the designation if it's not met, is not realistic. $\endgroup$ – Suresh Venkat Mar 25 '11 at 22:44

Ignoring Tsuyoshi's somewhat flame throwing premise, I don't see how this question remains unclosed. The OP has admitted already that this is a homework-puzzle-style question, and so it doesn't fall into the category of 'easy question from practitioner' that we would like to encourage.

I'd vote to close this question right now. It's somewhat moot because it has answers, but it's important to make things clear. As an aside, I don't think we are enforcing 'research level' inconsistently: it's just a fact of life that this is somewhat fuzzy (as Raphael indicates), and we'll have to judge cases on their own basis.

  • 2
    $\begingroup$ My impression is that the understandable desire to judge questions based on their motive complicates matters. If the question could have been an 'easy question from practitioner' we should answer it. $\endgroup$ – Marcus Ritt Mar 17 '11 at 12:40
  • 2
    $\begingroup$ I also think trying to judge questions by motive gets problematic. I think a possible criteria is if the question could lead to non-trivial non-obvious answers which I think this question did. $\endgroup$ – Mugizi Rwebangira Mar 17 '11 at 14:01
  • 3
    $\begingroup$ @Mugizi: IMO, one of the main differences between serious research and puzzle solving is the motivation. It's not the case that puzzle solving requires less ingenuity than research. In fact, it's probably the opposite. However, puzzles tend to not be part of a bigger endeavour, they tend to not build on one--another, they tend to have not much motivation apart from "it's cool." $\endgroup$ – Radu GRIGore Mar 17 '11 at 19:09
  • $\begingroup$ It's not a matter of puzzle or not, it is a matter if there is something to be gained or discussed instead of being intelligent question-answer systems. For example, chess is a very interesting puzzle. A question about tactics should be dismissed as off-topic, while heuristics on the general nXn chess problem would be a great topic. It's more a question of relevance than difficulty. $\endgroup$ – chazisop Mar 20 '11 at 6:34

The way I understand StackExchange websites is that they are run by the community. If you like a question, you vote it up. If you do not like a question, you vote for it to be closed (or vote it down, if it is formulated poorly). Ultimately, the community decides. For the question under discussion, the community seems to have decided in favour of keeping the question.

"Jumping to meta" should be probably only be used in exceptional circumstances, and it shouldn't be done in a way that can be perceived flame-baiting (if that's even a word), by maligning the community and any individuals therein who have a different opinion.

... especially when the community opinion is not different.

  • 10
    $\begingroup$ I believe that I did the right thing by posting on meta because (1) it revealed a lot of disagreements among the users, and (2) this post received many comments and answers which could pollute the question if posted on main (see also Suresh’s post). $\endgroup$ – Tsuyoshi Ito Mar 17 '11 at 18:20
  • 6
    $\begingroup$ Yes, I think that meta is the place for such discussions, for the reasons Tsuyoshi mentioned. $\endgroup$ – Suresh Venkat Mar 17 '11 at 22:04
  • 3
    $\begingroup$ My concern is not whether meta is the place for such discussions, but whether this particular discussion should have started in the first place. $\endgroup$ – Dave Clarke Mar 18 '11 at 7:42
  • 6
    $\begingroup$ this is not entirely true. The Stack Overflow community LOVED "funniest programming cartoon" and it had thousands of upvotes. But it still wasn't welcome on our site... $\endgroup$ – Jeff Atwood Mar 18 '11 at 7:47
  • 1
    $\begingroup$ I'm not sure if Tsuyoshi's suggestion is a good idea or not, but I really didn't think he was trying to flame or agitate anyone. Obviously I don't speak for him, but I thought it was maybe a little harsh to suggest that he was flame-baiting and/or maligning the community. $\endgroup$ – Philip White Mar 18 '11 at 23:42
  • 1
    $\begingroup$ Jeff, you perfectly outline the problem here: the system and its mechanisms suggest a democratic process, but at the end of the day it is a small elite that defines and enforces scope (and other things). One could say the system is therefore inherently broken; at least the contradiction creates a lot of friction. $\endgroup$ – Raphael Mar 24 '11 at 22:23

I think we can be fairly relaxed about this instance. Here I intended to reformulate a few things said in this thread, to bring together some strands and maybe add some clarity, and then I suggest a rule which is not far, I think, from what we have been doing.


Observe that we might mean two different things by "research-level". Consider three kinds of question:

  1. Questions that every self-respecting, theoretically oriented comp-sci graduate student should be able to answer;
  2. Questions many TCSers whose expertise lies elsewhere will have difficulty with, but which yield easily to insights that are well-established in some domain of expertise;
  3. Questions that are open problems; original, worthy research problems; or previously solved problems whose solution is not widely known even among domain experts.

Level 1 is not appropriate here, level 3 is research level by any reasonable reckoning. But what about level 2? As Radu noted, questions of this sort are quite often interesting in the context of a problem in one TCS domain, but demand expert knowledge from another domain for their solution; these are clearly research-motivated questions, and the site would be poorer to reject these. So if we might mean just level 3 counts as research level, we might alternately say that levels 2 and 3 are appropriate to the site.

But level 2 will also include some grad school problems and puzzles like the question that led to this thread. Several people suggested that the motivation for a question might be used as a criteria to divide these level into worthy and unworthy. The issue here is that we do not demand that the motivation be provided for questions, so we have to decide on the basis of what we see. Thus as Marcus and others have said, judging motivation is problematic. It is not clear that there are other useful, principled criteria for dividing level 2 into good and bad.


There isn't much sign that level 2 questions have been a significant nuisance —here Tsuyoshi's concern seems to be to do with consistency— but in the long run they could be. I suggest we work according to the following criterion: level 2 questions situated in the context of any research interest are on topic. Level 2 questions that lack such motivation are in a grey area: we should encourage motivation, and we promise no consistency in the way we handle them. These questions will be closed if there are five people with close powers who are bothered by the question. It might be good to have a thread listing such closures.

Large grey areas are not good, but I think it would be worse to bar good questions or stipulate the unworkable as criteria. Can we do better?

  • $\begingroup$ I think that's reasonable. as for mechanics, what would it mean to have a 'thread listing closures' ? $\endgroup$ – Suresh Venkat Apr 19 '11 at 15:37
  • $\begingroup$ @Suresh: Someone starts a thread called something like "Tricky question closes" that works a bit like meta.cstheory.stackexchange.com/questions/76/…. $\endgroup$ – Charles Stewart Apr 19 '11 at 17:13
  • $\begingroup$ I vote we enshrine this as policy $\endgroup$ – Suresh Venkat Apr 19 '11 at 17:50
  • $\begingroup$ If level 1 is clearly off topic and level 3 is clearly on topic, then neither defines the scope of the website. It seems that the final deciding criterion is not level but motivation. Because of that, we should really reconsider the current practice of mindlessly using “research-level” as a magical word to describe the scope of this website. “Research-oriented” or something along this line looks more appropriate. $\endgroup$ – Tsuyoshi Ito Apr 20 '11 at 1:55
  • $\begingroup$ I am not sure that I understand the problem we are trying to solve here. Type 2 questions which are not type 1 are already on topic AFAIK. The objective of restricting the scope to research level questions was keeping the site interesting for researchers and that is what we should keep in mind. We have made an exception about reasonable number of applications of theory questions and that is what we mainly ask for motivation as we have decided in a previous discussion. I think using research level as description of site is working quite well on cstheory as it is on MO and don't see any reason $\endgroup$ – Kaveh Apr 20 '11 at 2:13
  • $\begingroup$ for changing it. In general the TCS questions which can be answered by material covered in a typical undergrad course or textbook are clearly off-topic (as long as they are not application of theory questions), TCS questions above that level are not clearly off-topic (excluding special exceptions like asking for general correctness of unpublished preprints). $\endgroup$ – Kaveh Apr 20 '11 at 2:17
  • $\begingroup$ ps: I also ask for motivation when a new user asks a questions that looks suspicious (e.g. looks like a veiled attempted at P vs NP) and I try to ask it in a nice way so it does not create bad feelings. Also note that we are not dividing questions into "worthy and unworthy", off-topic for cstheory is not unworthy, that is a something we clearly would like to avoid. $\endgroup$ – Kaveh Apr 20 '11 at 2:23
  • $\begingroup$ @Tsuyoshi: I like the suggestion of using the term "research-oriented". It makes asking for motivation that bit easier. $\endgroup$ – Charles Stewart Apr 20 '11 at 5:25
  • $\begingroup$ @Kaveh: Saying all level 2 questions are in (hopefully the intersection of level 1 and 2 is small) is a reasonable position. I'm a bit worried about asking questions from, say, these assignments, which are clearly level 2. Where does your text come from? It's not from the FAQ. $\endgroup$ – Charles Stewart Apr 20 '11 at 5:31
  • $\begingroup$ @Charles, it is not an official text (at least I don't remember so), but we had a discussion where applications of theory in other areas and it seems to me that type 2 are closer than them to the scope. I understand your point, we don't want the site to become full of graduate assignment (or graduate assignment-level) questions, and I agree with it. I think this is what happened: $\endgroup$ – Kaveh Apr 20 '11 at 5:51
  • $\begingroup$ Originally we were forbidding homework questions, but that was creating tension and needed lots of judging if something is a homework. So we moved to home-work level (so it does not need to be really a homework but just something that could be a homework), the problem with that: it causes tension with users since it gives the feeling that their questions is low-level. So we changed homework-level to not-research-level and I doubt anyone would feel bad if we tell him that the question is not research-level. $\endgroup$ – Kaveh Apr 20 '11 at 5:54
  • $\begingroup$ But the problem now is where to draw the line. I think we agree that questions at the level of typical undergrad textbook/course is off-topic. Above that it is difficult to say if something is really a homework or a genuine question that came up in research. I don't like judging motivations, it is difficult and it is not difficult to circumvent, so I prefer if we keep it minimal. (I don't want to start judging if something is homework or not based on motivation.) (ps: I now see the point of your answer.) $\endgroup$ – Kaveh Apr 20 '11 at 6:01
  • $\begingroup$ I don't have strong feelings about research-level vs research-oriented, I just feel that the former is easier to understand for new users but if you think the later is better I am personally OK with using it in place of research-level. $\endgroup$ – Kaveh Apr 20 '11 at 7:57

You must log in to answer this question.

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