Area 51 » Science

181

followers

Announcements

This is a proposal to explore whether it'd be useful to create a separate TheoryOverflow site dedicated to research-level questions in theoretical computer science, broadly interpreted to include algorithms, complexity, approximation, randomness, quantum, algorithmic game theory, computational geometry, computability, and the like. Please follow the discussion if interested, suggest examples for good and bad questions, and add your thoughts on whether or not such a site would be useful for the theory community. – Anand Kulkarni Jun 23 '10 at 2:38

What about type theorists, programming language semanticists, automated reasoners and the like? Are they all included? Similarly, George's point is a good one: compiler design and operating system design often overlap extensively with TCS. How wide a topic is theoretical computer science going to be considered? – Dominic Mulligan Jun 23 '10 at 11:47

My inclination would be to take a broad view of theory and encourage theory questions from these domains. The main criteria I'd use in deciding whether a question seemed suitable would be first, whether the question could be better answered on Stack or MathOverflow, and second, whether the question would be of interest to or answerable by the theory community. Suggest some sample questions from these areas! – Anand Kulkarni Jun 24 '10 at 8:12

show 4 more announcements

41 Example Questions (9 closed)

active newest votes

up vote 21 down vote

added by Anand Kulkarni Jun 23 '10 at 2:21

MathOverflow presently supports questions of this nature that are oriented towards explanation and education rather than directed towards solving a specific research problem. Presumably, the asker would have a specific difficulty in mind they'd like to see resolved. – Anand Kulkarni Jun 23 '10 at 2:29

up vote 20 down vote

added by Anand Kulkarni Jun 23 '10 at 2:03

A reasonable answer could provide either a proof of undecidability, an algorithm for the problem, or some discussion of why the question is expected to be formally difficult. – Anand Kulkarni Jun 23 '10 at 2:23

up vote 20 down vote

added by Chris W. Rea Jun 23 '10 at 12:21

up vote 20 down vote

added by goldsz Jun 25 '10 at 0:41

I hope this is on topic, and that the plan isn't to just pose open research questions. – goldsz Jun 25 '10 at 0:44

Everyday expert-level questions like this that arise in the course of research seem reasonable to me, and MathOverflow has succeeded by encouraging exactly these types of questions. Hopefully nobody will simply ask for answers to questions that they know to be open without being more specific; as in MathOverflow's criteria (mathoverflow.net/faq#whatnot), the goal could be to obtain help with a particular approach in a specific context. – Anand Kulkarni Jun 25 '10 at 9:56

up vote 19 down vote

added by Chris W. Rea Jun 23 '10 at 12:18

Somebody voted "not a good example". Boooo ;-) – Chris W. Rea Jun 26 '10 at 16:12

Problems in NP are decision problems (i.e. yes/no questions). So hopefully the body of the question describes how to phrase "integer factorization" as a decision problem. – Douglas S. Stones Jun 26 '10 at 23:08

up vote 15 down vote

added by Robert Harvey Jun 24 '10 at 16:34

up vote 11 down vote

added by Jacques Carette Jun 24 '10 at 1:58

Why is this being considered an off topic question? It's a classic question in programming language design theory. – Dominic Mulligan Jun 24 '10 at 9:32

Indeed - I proposed it thinking it was on-topic. – Jacques Carette Jun 24 '10 at 11:48

My first reaction was that this was NOT a good question, but rather a simple Google query, which leads immediately to a Wikipedia page. But the WIkipedia page is particularly bad, which makes this a good question! – JeffE Jun 24 '10 at 15:56

Is there no good existing reference? I will remove my off-topic vote. – Robert Harvey Jun 24 '10 at 18:25

What "the expression problem" is keeps getting refined as people explore it. It is not really 'settled' (yet!). – Jacques Carette Jun 24 '10 at 21:53

up vote 11 down vote

added by JeffE Jun 24 '10 at 16:08

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a shuffle of MISIPPI and SSISI. Let me call a string square if it is a shuffle of two identical strings. For example, ABCABDCD is square, because it is a shuffle of ABCD and ABCD, but the string ABCDDCBA is not square. Is there a fast algorithm to determine whether a string is square, or is it NP-hard? (The obvious dynamic programming approach doesn't seem to work.) – JeffE Jun 24 '10 at 16:16

up vote 8 down vote

added by Jacques Carette, edited by Robert Harvey Jun 24 '10 at 18:34

I really don't see what this have to do with algorithms at all. The characteristics of such PL can be clearly defined, but advantages and disadvantages in PL are often of a subjective nature. – Daniel C. Sobral Jun 25 '10 at 17:11

I don't think this needs to have anything to do with algorithms as long as it's a legitimate question in the theory of program languages – Suresh Jun 25 '10 at 17:16

I agree with Suresh. Granted, a pl theorist who wants a flame war would say "decidable type checking" lets us actually run all good (well typed) programs, and thus "haskell is better than java", but despite that possible response theres some really cool math going on in analyzing these type systems, and thats pure theory :) – Carter Tazio Schonwald Jun 25 '10 at 22:54

I think 'is haskell better than java' is a good off topic question ;) – Suresh Jun 25 '10 at 23:05

@Daniel: This is TCS not algorithms. I considered this a legit question on programming languages. – Jacques Carette Jun 26 '10 at 21:21

up vote 7 down vote

added by Suresh Jun 23 '10 at 5:41

this is a reference request probably, but given the dizzying array of methods in this area, it's a good question to solicit expertise in (from one expert to another) – Suresh Jun 23 '10 at 5:41

up vote 7 down vote

added by Suresh Jun 23 '10 at 22:52

up vote 6 down vote

added by Jacques Carette Jun 24 '10 at 1:59

up vote 6 down vote

added by JeffE Jun 24 '10 at 16:22

	Believe it or not, this question is open. – JeffE Jun 24 '10 at 16:23
	There is a polynomial-time algorithm, via group theory, to decide whether the cube is solvable. – JeffE Jun 24 '10 at 16:24

up vote 6 down vote

added by Ryan Williams Jun 25 '10 at 16:35

up vote 5 down vote

added by JeffE Jun 24 '10 at 16:00

up vote 4 down vote

added by Anand Kulkarni Jun 23 '10 at 2:12

that's a bit borderline for a good post, on second thought. – Suresh Jun 23 '10 at 5:47

up vote 4 down vote

added by Roy Maclean Jun 24 '10 at 9:56

up vote 3 down vote

added by Roy Maclean Jun 24 '10 at 10:06

up vote 3 down vote

added by Akhil Mathew Jun 24 '10 at 15:40

up vote 3 down vote

added by Ryan Williams Jun 25 '10 at 16:22

Note: There could be multiple answers as there probably are several incomparable classes that satisfy the question. Knowing this antichain may be useful, though. – Ryan Williams Jun 25 '10 at 16:25

up vote 2 down vote

added by Anand Kulkarni Jun 24 '10 at 8:04

As posed, this type of question would be more suitable for MathOverflow. – Anand Kulkarni Jun 24 '10 at 8:05

it's a fine line. – Suresh Jun 24 '10 at 9:43

From the Area51 FAQ: Don't worry about whether a question might be asked on another site. Your goal is to make the best possible site for this community. – Robert Harvey Jun 24 '10 at 22:31

Good point! A better criteria might be whether such questions are suitably interesting for theorists; this one might be, depending on the context. Are there any better examples of suitably off-topic mathematics questions? Perhaps pure topology or analysis? – Anand Kulkarni Jun 25 '10 at 0:27

up vote 2 down vote

added by Roy Maclean Jun 24 '10 at 9:35

up vote 2 down vote

added by Roy Maclean Jun 24 '10 at 9:53

up vote 2 down vote

added by JeffE Jun 24 '10 at 16:01

closed as off topic by Anand Kulkarni, goldsz, user6092, SamiD, Ryan Williams Jun 25 '10 at 23:53

This question does not relate to the topic of the proposal.
It was closed as part of an automated migration of off-topic to close votes on September 29, 2011.

This is another good example of a question that would be too elementary, since it's covered by a suitable Wikipedia article / Google search. en.wikipedia.org/wiki/General_position – Anand Kulkarni Jun 25 '10 at 0:14

up vote 2 down vote

added by Ryan Williams Jun 25 '10 at 16:27

Every once in a while, a complexity theorist comes across a weird definition of a complexity class (where the languages must satisfy property BLAH if x is in the language, and property BLAH' if x isn't in the language). The community should be helpful in quickly determining where this class falls within the Complexity Zoo (qwiki.stanford.edu/wiki/Complexity_Zoo) – Ryan Williams Jun 25 '10 at 16:29

up vote 2 down vote

added by Martin Schwarz Jun 26 '10 at 8:48

up vote 2 down vote

added by Michael Jun 27 '10 at 17:18

up vote 2 down vote

added by incrediman Jun 28 '10 at 4:02

up vote 1 down vote

added by SamiD Jun 25 '10 at 19:18

	Sometimes the intuition behind an "established" belief is difficult to trace for a novice (or even a non-novice) so I think such a question should be on-topic even though potential answers are necessarily subjective in the absence of a proof, one way or the other. – SamiD Jun 25 '10 at 19:31
	could be a good community wiki-type question. alas I have no more positive votes to give. More voting, people ! – Suresh Jun 25 '10 at 19:40

up vote 1 down vote

added by miku Jun 26 '10 at 13:07

Can you expand? It's hard to tell what your question is. – Jacques Carette Jun 26 '10 at 21:26

up vote 0 down vote

added by Suresh Jun 23 '10 at 5:46

closed as off topic by Anand Kulkarni, andreypopp, Sindri Traustason, Chris W. Rea, ire_and_curses Jun 23 '10 at 16:05

This question does not relate to the topic of the proposal.
It was closed as part of an automated migration of off-topic to close votes on September 29, 2011.

this would be an example of an off-topic post. Actually I just took it from stackoverflow :). But I'd expect lots of posts along these lines, and they would not be appropriate – Suresh Jun 23 '10 at 5:47

much as I appreciate the upvotes, I'd prefer that any upvotes at this point be redirected to other good questions to get them above 20. – Suresh Jun 26 '10 at 7:45

up vote 0 down vote

added by bdonlan Jun 23 '10 at 17:33

closed as off topic by Suresh, ShreevatsaR, Dominic Mulligan, Daniel Egeberg, asalamon74 Jun 24 '10 at 16:58

This question does not relate to the topic of the proposal.
It was closed as part of an automated migration of off-topic to close votes on September 29, 2011.

up vote 0 down vote

added by Jacques Carette Jun 24 '10 at 1:56

closed as off topic by ShreevatsaR, Anand Kulkarni, Dominic Mulligan, JeffE, Chris W. Rea Jun 24 '10 at 18:33

This question does not relate to the topic of the proposal.
It was closed as part of an automated migration of off-topic to close votes on September 29, 2011.

the thing about this is that it falls under the umbrella of applied programming language theory... eg this could be reformulated as "how do I turn specfications of my code in theorem prover proof goals?" – Carter Tazio Schonwald Jun 25 '10 at 22:50

up vote 0 down vote

added by goldsz Jun 25 '10 at 0:22

closed as off topic by Daniel C. Sobral, John Moeller, Gianluca Della Vedova, Daniel Trebbien, Alan Hogue Jun 26 '10 at 1:03

This question does not relate to the topic of the proposal.
It was closed as part of an automated migration of off-topic to close votes on September 29, 2011.

I'm not sure if this is the right wording for it. But should this topic include meta questions about the field of computer science? – goldsz Jun 25 '10 at 0:23

This would be a better question (with a different answer?) if it said theoretical computer science. – JeffE Jun 25 '10 at 3:56

up vote 0 down vote

added by Suresh Jun 25 '10 at 17:18

closed as off topic by JeffE, SamiD, Zeyu, Parasaran, Carlos Scheidegger Jun 26 '10 at 15:28

This question does not relate to the topic of the proposal.
It was closed as part of an automated migration of off-topic to close votes on September 29, 2011.

I actually intend this as an off-topic question, just to keep out the cranks. – Suresh Jun 25 '10 at 17:18

Actually if we stomp out the proof on TheoryOverflow, it would save time for the editors and reviewers of JACM/STOC/FOCS/etc. Not everyone who comes up with these things are necessarily cranks, either ;) – Ryan Williams Jun 25 '10 at 18:29

he he. crowd sourced crank control. I like it. And I think the phrasing of the question "it's your job to find my bugs" usually demarcates the cranks from the serious researchers :) – Suresh Jun 25 '10 at 19:40

up vote 0 down vote

added by Anand Kulkarni Jun 25 '10 at 17:59

closed as off topic by JeffE, SamiD, Carter Tazio Schonwald, Suresh, Carlos Scheidegger Jun 26 '10 at 15:28

This question does not relate to the topic of the proposal.
It was closed as part of an automated migration of off-topic to close votes on September 29, 2011.

An example of an off-topic mathematical question. From MathOverflow: mathoverflow.net/questions/29512/… – Anand Kulkarni Jun 25 '10 at 17:59

up vote 0 down vote

added by Donal Fellows Jun 26 '10 at 16:20

I would like to consider this on-topic, but the question is too short as it stands. One could easily expand this question into both something that is on-topic as well as pure quackery. – Jacques Carette Jun 26 '10 at 21:24