Most Popular
1500 questions
39
votes
13 answers
Using error-correcting codes in theory
What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: Goldreich-Levin theorem about hard core bit, Trevisan's construction of extractor and amplification of hardness of boolean…
ilyaraz
- 1,569
- 18
- 33
38
votes
6 answers
Grid $k$-coloring without monochromatic rectangles
Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known.
Anyone feel up to trying 5-colorings? ;)
The following question arises out of Ramsey…
Daniel Apon
- 6,001
- 1
- 37
- 53
38
votes
4 answers
What is the smallest result you publish on ArXiv?
In essence, the question is:
What is the least publishable unit for the ArXiv?
Of particular interest are fields that use the ArXiv extensively such as quantum computing. But comments on other fields and preprint services (like, ECCC & ePrint) are…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
38
votes
3 answers
Extended Church-Turing Thesis
One of the most discussed questions on the site has been What it Would Mean to Disprove the Church-Turing Thesis. This is partly because Dershowitz and Gurevich published a proof of the Church-Turing Thesis is the Bulletin of Symbolic Logic in…
Aaron Sterling
- 6,994
- 6
- 42
- 74
38
votes
2 answers
Multiplying n polynomials of degree 1
The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time.
You can do $O(n \log^2 n)$ time by applying FFT in a tree fashion.…
Mihai
- 1,870
- 13
- 14
38
votes
17 answers
Conjectures implying Four Color Theorem
Four Color Theorem (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are computer-assisted and quite intimidating.
There are…
Shiva Kintali
- 10,578
- 41
- 74
38
votes
3 answers
Consequences of Factoring being in P?
Factoring is not known to be NP-complete. This question asked for consequences of Factoring being NP-complete. Curiously, no one asked for consequences of Factoring being in P (maybe because such a question is trivial).
So my questions are:
Which…
Giorgio Camerani
- 6,842
- 1
- 34
- 64
38
votes
2 answers
Axioms necessary for theoretical computer science
This question is inspired by a similar question about applied mathematics on mathoverflow, and that nagging thought that important questions of TCS such as P vs. NP might be independent of ZFC (or other systems). As a little background, reverse…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
38
votes
8 answers
Higher-order algorithms
Most of the well-known algorithms are first-order, in the sense that their input and output are "plain" data.
Some are second-order in a trivial way, for example sorting, hashtables or the map and fold functions: they are parameterized by a…
jkff
- 8,941
- 3
- 23
- 33
38
votes
7 answers
Books on programming language semantics
I've been reading Nielson & Nielson's "Semantics with Applications", and I really like the subject. I'd like to have one more book on programming language semantics -- but I really can get only one.
I took a look at the Turbak/Gifford book, but it's…
Jay
- 982
- 7
- 16
38
votes
4 answers
Interactive proofs for levels of the polynomial hierarchy
We know that if you have a PSPACE machine, it's powerful enough to give an interactive proof of any level the polynomial hierarchy. (And if I remember right, all you need is #P.) But suppose you want to give an interactive proof of membership in a…
Peter Shor
- 24,763
- 4
- 93
- 133
38
votes
13 answers
Inspirational talk for final year high school pupils
I am often asked by my department to give talks to final year high school pupils about the more mathematical elements of computer science. I do my best to pick topics from TCS which might inspire their interest (which mostly involves something to do…
Simd
- 3,902
- 20
- 49
38
votes
3 answers
Max-cut with negative weight edges
Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find:
$$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$
If the weight function is non-negative (i.e. $w(e) \geq 0$…
Aaron Roth
- 9,870
- 1
- 43
- 68
38
votes
4 answers
Examples where the uniqueness of the solution makes it easier to find
The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. That is, the solution, if any, is unique in this…
Andras Farago
- 11,396
- 37
- 70
38
votes
7 answers
What is the oldest open problem in TCS?
This problem is inspired by this MO question, which I thought was very interesting.
What is the oldest open problem in TCS?
Clearly this question needs some clarification.
First, what is TCS? I think the existence of odd perfect numbers is not…
Robin Kothari
- 13,617
- 2
- 60
- 116