Most Popular
1500 questions
65
votes
11 answers
What are good references to understanding the proof of the PCP theorem?
I'm familiar with a lot of results that use the PCP theorem (mainly in approximating algorithms), but I've never come across a clear explanation of the PCP theorem (ie, that $\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1))$).
What are good papers/books…
Alexandre Passos
- 1,459
- 12
- 20
65
votes
1 answer
More on PH in PP?
A recent question by Huck Bennett asking whether the class PH was contained in the class PP, received somewhat contradictory answers (all true, it seems). On one hand, several oracle results were given to the contrary, and on the other Scott…
Noam
- 9,369
- 47
- 58
65
votes
10 answers
One Stack, Two Queues
background
Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no satisfactory result came up. I remember the course TA…
Sadeq Dousti
- 16,479
- 9
- 69
- 152
65
votes
5 answers
Problems that can be used to show polynomial-time hardness results
When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find the polynomial time algorithm. It's not that I…
Robin Kothari
- 13,617
- 2
- 60
- 116
64
votes
5 answers
Overarching reasons why problems are in P or BPP
Recently, when talking to a physicist, I claimed that in my experience, when a problem that naively seems like it should take exponential time turns out nontrivially to be in P or BPP, an "overarching reason" why the reduction happens can typically…
Scott Aaronson
- 13,733
- 2
- 62
- 68
63
votes
8 answers
What is the complexity class most closely associated with what the human mind can accomplish quickly?
This question is something I've wondered about for a while.
When people describe the P vs. NP problem, they often compare the class NP to creativity. They note that composing a Mozart-quality symphony (analogous to an NP task) seems much harder…
user1338
63
votes
4 answers
Evidence that matrix multiplication can be done in quadratic time?
It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple:
What reasons do we have for believing that $\omega = 2$?
I'm aware of fast algorithms like Coppersmith-Winograd,…
Steve Flammia
- 813
- 8
- 12
63
votes
12 answers
Parameterized complexity from P to NP-hard and back again
I'm looking for examples of problems parametrized by a number $k \in \mathbb{N}$, where the problem's hardness is non-monotonic in $k$. Most problems (in my experience) have a single phase transition, for example $k$-SAT has a single phase…
mikero
- 2,799
- 22
- 23
62
votes
33 answers
Small steps for better TCS conferences?
Often, when we take part in TCS conferences, we notice some little details that we wish the conference organisers would have taken care of. And when we are organising conferences, we have already forgotten it.
Hence the question: Which small steps…
Jukka Suomela
- 11,500
- 2
- 53
- 116
62
votes
13 answers
Open problems on the frontiers of TCS
In the thread Major unsolved problems in theoretical computer science?, Iddo Tzameret made the following excellent comment:
I think we should distinguish between major open problems that are viewed as fundamental problems, like $ P\neq NP $, and…
Robin Kothari
- 13,617
- 2
- 60
- 116
61
votes
7 answers
How to shoot down your proofs
What are general guidelines for checking your proofs? I believe this is important for graduate students like me. I already know what we need to do to prove something, but you always have to check everything before you send it out. Even to your own…
Marcos Villagra
- 3,290
- 27
- 45
61
votes
14 answers
Information Theory used to prove neat combinatorial statements?
What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ?
Some examples I can think of are related to lower bounds for locally decodable codes, e.g., in this paper: suppose that for a…
Dana Moshkovitz
- 10,979
- 1
- 50
- 77
61
votes
3 answers
Realizability theory: difference in power between Lambda calculus and Turing Machines
I have three related subquestions, which are highlighted by bullet points below (no, they could not be split, if you are wondering).
Andrej Bauer wrote, here, that some functions are realizable through a Turing machine, but not through…
Blaisorblade
- 2,059
- 21
- 29
60
votes
6 answers
How to get a job
I'm new to the site. On mathoverflow this would be community wiki, but I don't see how to set that here. Not a research question, but hopefully of interest to professional theoretical computer scientists.
I am a 2nd year grad student in theory, and…
Vipul
59
votes
15 answers
Open access journals
With the advent of internet (and common sense) there is more and more demand for open-access research. Several researchers (including me) find it frustrating that published peer-reviewed research articles are behind paywalls. I am looking for…
Shiva Kintali
- 10,578
- 41
- 74