Stack Exchange
log in sign up chat discuss faq users badges

Area 51 » Science

definition commitment beta
181
followers

Theoretical Computer Science

Launched Q&A site for theoretical computer scientists and researchers in related fields

Announcements

5  
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
5  
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
7  
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
27
votes
6
answers

Two level model (MO/Math.SE) vs one level model (SO)

dec 8 '11 at 15:53 Community♦ 1
15
votes
4
answers

Scope of Cryptography proposal overlaps with other existing sites

jul 13 '11 at 0:24 Community♦ 1

discuss this proposal

41 Example Questions (9 closed)

active newest votes
up vote 21 down vote
How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?
added by Anand Kulkarni Jun 23 '10 at 2:21
link
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
Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?
added by Anand Kulkarni Jun 23 '10 at 2:03
link
1  
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
Are hash functions such as SHA-1, SHA-256 etc. provably "one-way" in their complexity, i.e. easy to compute and provably hard to reverse?
added by Chris W. Rea Jun 23 '10 at 12:21
link
up vote 20 down vote
In [ACM citation] I'm confused how the authors arrived at [assertion] from equation 2?
added by goldsz Jun 25 '10 at 0:41
link
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
Is integer factorization an NP-complete problem? What notable reference works have covered this?
added by Chris W. Rea Jun 23 '10 at 12:18
link
Somebody voted "not a good example". Boooo ;-) – Chris W. Rea Jun 26 '10 at 16:12
1  
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
Is there a way to solve [this particular computing problem] in O(n) or O(log n)?
added by Robert Harvey Jun 24 '10 at 16:34
link
up vote 11 down vote
What is "the expression problem"?
added by Jacques Carette Jun 24 '10 at 1:58
link
2  
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
How hard is it to unshuffle a string? (See comments for details.)
added by JeffE Jun 24 '10 at 16:08
link
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
What are the advantages and disadvantages of a programming language with undecidable type checking?
added by Jacques Carette, edited by Robert Harvey Jun 24 '10 at 18:34
link
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
1  
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
1  
I think 'is haskell better than java' is a good off topic question ;) – Suresh Jun 25 '10 at 23:05
1  
@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
Which extractor construction provides the best tradeoff between randomness, time and space ?
added by Suresh Jun 23 '10 at 5:41
link
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
What is the best algorithm for deciding membership in the intersection of two context-free languages
added by Suresh Jun 23 '10 at 22:52
link
up vote 6 down vote
What are 'shallow' and 'deep' embeddings of one language into another?
added by Jacques Carette Jun 24 '10 at 1:59
link
up vote 6 down vote
Is it NP-hard to find the shortest sequence of rotations that solves a given scrambled (nxnxn) Rubik's Cube?
added by JeffE Jun 24 '10 at 16:22
link
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
Which sorting algorithm is fastest on the uniform distribution (each n-element permutation chosen with 1/n! probability)?
added by Ryan Williams Jun 25 '10 at 16:35
link
up vote 5 down vote
What is a "dynamically optimal" binary tree?
added by JeffE Jun 24 '10 at 16:00
link
up vote 4 down vote
Which heuristic for set cover has the lowest average-case complexity under the following distribution of inputs?
added by Anand Kulkarni Jun 23 '10 at 2:12
link
that's a bit borderline for a good post, on second thought. – Suresh Jun 23 '10 at 5:47
up vote 4 down vote
Is Burgin's concept of Super-recursive algorithms useful or is it crankery ?
added by Roy Maclean Jun 24 '10 at 9:56
link
up vote 3 down vote
Has there been any work done on Reverse Complexity ? i.e. for a given expression finding a problem or algorithm with that complexity.
added by Roy Maclean Jun 24 '10 at 10:06
link
up vote 3 down vote
Why are all Blum complexity measures equivalent?
added by Akhil Mathew Jun 24 '10 at 15:40
link
up vote 3 down vote
What's the smallest complexity class that's known to properly contain LOGSPACE?
added by Ryan Williams Jun 25 '10 at 16:22
link
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
Given a d-dimensional n-facet polytope P and a halfspace H containing no facet of P, what is the maximum number of vertices of P that can lie in H?
added by Anand Kulkarni Jun 24 '10 at 8:04
link
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
1  
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
There is smoothed analysis of particular *algorithms* but would it make sense to try calculating the smoothed complexity of a problem ?
added by Roy Maclean Jun 24 '10 at 9:35
link
up vote 2 down vote
Are there concepts in the TCS of digital computation that don't or couldn't have equivalents in the TCS of analog computation and vice versa?
added by Roy Maclean Jun 24 '10 at 9:53
link
up vote 2 down vote
I'm reading a computational geometry paper that talks about "general position". What does that mean? [closed]
added by JeffE Jun 24 '10 at 16:01
link

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
Is this a new complexity class?
added by Ryan Williams Jun 25 '10 at 16:27
link
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
What is the new key insight in Moser's recent constructive proof of the Lovász Local Lemma?
added by Martin Schwarz Jun 26 '10 at 8:48
link
up vote 2 down vote
Has this problem been studied before? <Description of non-trivial TCS Problem>. I suspect it has, but still haven't found a reference.
added by Michael Jun 27 '10 at 17:18
link
up vote 2 down vote
Has it been proven that Grover's algorithm is an optimal solution to the quantum search problem it solves? If so how, and if not why hasn't it been?
added by incrediman Jun 28 '10 at 4:02
link
up vote 1 down vote
What are the reasons for (dis)believing DLog (or your favorite small complexity class) is strictly in NLog (or your favorite large complexity class)?
added by SamiD Jun 25 '10 at 19:18
link
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
Implementations of a General Problem Solver?
added by miku Jun 26 '10 at 13:07
link
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
I want to write a program to solve a maze. How should I do it ? [closed]
added by Suresh Jun 23 '10 at 5:46
link

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.

2  
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
2  
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
I wrote this implementation of quicksort. Why does it seem to take exponential time? [closed]
added by bdonlan Jun 23 '10 at 17:33
link

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
Which specification language (currently) has the best tool support? [closed]
added by Jacques Carette Jun 24 '10 at 1:56
link

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
I'm interested in going to Graduate School for Computer Science. Any [Advice/Cautionary Tales]? [closed]
added by goldsz Jun 25 '10 at 0:22
link

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
3  
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
Where is the bug in my amazing proof that P != NP ? [closed]
added by Suresh Jun 25 '10 at 17:18
link

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
2  
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
When is a sheaf of smooth functions acyclic? [closed]
added by Anand Kulkarni Jun 25 '10 at 17:59
link

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
What are the consequences of applying a Galois Connection-based domain abstraction to CTL* model checking?
added by Donal Fellows Jun 26 '10 at 16:20
link
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
up vote 0 down vote
What is the best (animated) graphic to describe algorithm xyz?
added by tobiw Jun 27 '10 at 6:59
link
up vote -1 down vote
What is the difference between NP-Hard and NP-Complete ?
added by goldsz Jun 24 '10 at 16:10
link
It seems to me that this question could be answered immediately by a quick Google search, no? – Anand Kulkarni Jun 24 '10 at 22:15
Let me Wikipedia that for you: en.wikipedia.org/wiki/… – JeffE Jun 24 '10 at 22:42
Ok. So is it off topic? Or just not a good example? This question came from area51.stackexchange.com/proposals/5120/… – goldsz Jun 25 '10 at 0:14
not a good example because it can be googled, and it's often a homework problem. – Suresh Jun 25 '10 at 4:55
1  
It's a good example of what we know we don't want to see on the site. – Anand Kulkarni Jun 25 '10 at 17:54
up vote -1 down vote
At your university, is computable analysis studied in the CS dept or the math dept or both ? [closed]
added by Roy Maclean Jun 25 '10 at 2:37
link

closed as off topic by Daniel C. Sobral, John Moeller, JeffE, sepp2k, Gianluca Della Vedova Jun 25 '10 at 19:22

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.

1 2 next

This site has

Launched!

This Stack Exchange site's beta was successful, so it launched 10 years ago.

proposed by

Anand Kulkarni
4,749●2●8●32

10 years ago

viewed

23,691 times

latest activity

10 years ago

followers

users also following

13.8% Mathematics
10.5% TeX, LaTeX and fr...
9.4% Statistical Analysis
8.8% User Experience
37.0% only this proposal

followers active in

63.5% Theoretical Compu...
61.9% Stack Overflow
41.4% Mathematics
35.9% Meta Stack Overflow
34.3% Super User
30.9% Server Fault

recent followers

added Aug 16 '10 at 4:09
Aryabhata
106k●14●255●413
added Aug 15 '10 at 6:47
Martin Hohenberg
51●1
added Aug 14 '10 at 23:44
Nikolai Prokoschenko
12.5k●11●91●175
added Aug 14 '10 at 11:38
Michael Ekstrand
35.3k●15●123●243
added Aug 14 '10 at 7:18
Bolo
16.2k●8●58●119
added Aug 13 '10 at 17:28
svick
265k●63●583●927
added Aug 12 '10 at 13:34
Rehno Lindeque
4,549●2●22●45
added Aug 11 '10 at 23:24
ars
117k●22●169●189
added Aug 11 '10 at 20:56
viksit
6,953●9●39●55
added Aug 11 '10 at 15:14
Michael
456●1●9
added Aug 11 '10 at 7:46
ldunn
52●1
added Aug 11 '10 at 1:42
Eli Frey
4,134●4●32●54
added Aug 10 '10 at 21:18
Diego de Estrada
4,394●2●42●72
added Aug 9 '10 at 22:55
Edza
1,211●2●12●25
added Aug 9 '10 at 16:48
jrista
103k●29●269●500
added Aug 9 '10 at 8:06
gphilip
4,275●6●31●72
added Aug 6 '10 at 18:27
morfu
2,214●1●41
added Aug 6 '10 at 6:22
mariachris
112●10
added Aug 5 '10 at 21:50
Jonas
5,533●6●38●66
added Aug 5 '10 at 20:42
Kelly S. French
15.4k●9●85●162
added Aug 5 '10 at 20:13
chanchal1987
11.6k●19●84●210
added Aug 4 '10 at 10:29
Shawn Chin
95.1k●22●221●352
added Aug 3 '10 at 9:14
Srinivas Reddy Thatiparthy
11.4k●7●50●100
added Aug 2 '10 at 17:23
Gelatin
31.2k●11●155●302
added Jul 31 '10 at 0:21
peeles
190●1●6
added Jul 29 '10 at 2:24
ecounysis
3,275●4●25●36
added Jul 28 '10 at 16:43
Paul Nathan
59.8k●41●212●370
added Jul 28 '10 at 15:35
Daniel Trebbien
40.5k●17●128●240
added Jul 27 '10 at 15:05
rgrig
8,934●1●60●134
added Jul 27 '10 at 8:45
Noldorin
175k●74●476●682
added Jul 26 '10 at 15:28
user12979
51●1
added Jul 26 '10 at 4:17
awshepard
3,617●2●26●50
added Jul 25 '10 at 18:43
Gian
13.4k●41●62
added Jul 24 '10 at 7:22
aditya
72●2
added Jul 23 '10 at 7:58
user12516
51●1
added Jul 22 '10 at 16:41
Vincent Ramdhanie
99.5k●24●142●200
added Jul 21 '10 at 13:41
Niel de Beaudrap
58.5k●13●189●380
added Jul 20 '10 at 21:47
Ashley Williams
1,053●5●18
added Jul 18 '10 at 6:35
user11366
51●1
added Jul 18 '10 at 3:07
Wei Hu
3,109●2●24●34
feed icon proposal feed
faq | blog | legal | privacy policy | contact us | feedback always welcome
site design / logo © 2021 Stack Exchange Inc; user contributions licensed under cc by-sa; see the licensing help page for more information.
rev 2021.2.22.577