Most Popular
1500 questions
37
votes
2 answers
Status of Impagliazzo's Worlds?
In 1995, Russell Impagliazzo proposed five complexity worlds:
1- Algorithmica: $P=NP$ with all the amazing consequences.
2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) but are efficiently solvable in the…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
37
votes
7 answers
What's the simplest noncontroversial 2-state universal Turing machine?
I'm wanting to encode a simple Turing machine in the rules of a card game. I'd like to make it a universal Turing machine in order to prove Turing completeness.
So far I've created a game state which encodes Alex Smith's 2-state, 3-symbol Turing…
AlexC
- 473
- 4
- 6
36
votes
6 answers
Journals with quick reviewing
Background: The motivation for this question is two-fold. First, I would like to get some hard facts to better understand the ongoing conferences vs. journals debate. Second, if this information was somewhere available, I could make a more informed…
Jukka Suomela
- 11,500
- 2
- 53
- 116
36
votes
6 answers
Have you ever realized you can't solve the homework you assigned?
This question is targeted at people who assign problems: teachers, student assistants, tutors, etc.
This has happened to me a handful of times in my 12-year career as a professor: I hurriedly assigned some problem from the text thinking "this looks…
Fixee
- 1,003
- 8
- 15
36
votes
2 answers
Consequences of $SAT \in BQP$
As a TCS amateur, I'm reading some popular, very introductory material on quantum computing. Here are the few elementary bits of information I've learned so far:
Quantum computers are not known to solve NP-complete problems in polynomial…
Giorgio Camerani
- 6,842
- 1
- 34
- 64
36
votes
14 answers
Book on Probability
While I have passed some courses on probability theory, both in the high school and the university, I have a hard time reading TCS papers when it comes to probability.
It seems that the authors of the TCS papers are very acquainted with probability.…
Incredible
- 463
- 6
- 10
36
votes
1 answer
Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers
I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "packing" and "covering" problems in nearly linear time, and…
Luca Trevisan
- 4,912
- 28
- 34
36
votes
8 answers
Collaborative tools for dummies/professors
Suppose that coauthors from two or more different institutions are writing a paper in latex, and would like to do better than repeatedly emailing drafts back and forth.
They realize they can open for free a dropbox account, share the password, and…
Luca Trevisan
- 4,912
- 28
- 34
36
votes
10 answers
Most important new papers in computational complexity
We often hear about classic research and publications in the field of computational complexity (Turing, Cook, Karp, Hartmanis, Razborov etc). I was wondering if there are recently published papers considered seminal and a must read. By recent I mean…
Yamar69
- 684
- 5
- 12
36
votes
4 answers
Why is "topological sorting" topological?
Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why is it not called "dependency sort" or something…
PartialOrder
- 463
- 5
- 7
36
votes
1 answer
Computational complexity of pi
Let
$L = \{ n : \text{the }n^{th}\text{ binary digit of }\pi\text{ is }1 \}$
(where $n$ is thought of as encoded in binary). Then what can we say about the computational complexity of $L$? It's clear that $L\in\mathsf{EXP}$. And if I'm not…
Scott Aaronson
- 13,733
- 2
- 62
- 68
36
votes
8 answers
Which definition of asymptotic growth-rate should we teach?
When we follow the standard textbooks, or tradition, most of us teach the following definition of big-Oh notation in the first few lectures of an algorithms class:
$$
f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n)…
slimton
- 1,570
- 14
- 18
36
votes
3 answers
NC = P consequences?
The Complexity Zoo points out in the entry on EXP that if L = P then PSPACE = EXP. Since NPSPACE = PSPACE by Savitch, as far as I can tell the underlying padding argument extends to show that $$(\text{NL} = \text{P}) \Rightarrow (\text{PSPACE} =…
András Salamon
- 19,000
- 3
- 64
- 150
36
votes
1 answer
Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$
Many believe that $\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$. However we only know that $\mathsf{BPP}$ is in the second level of polynomial hierarchy, i.e. $\mathsf{BPP}\subseteq \Sigma^ \mathsf{P}_2 \cap \Pi^ \mathsf{P}_2$. A step towards…
Kaveh
- 21,577
- 8
- 82
- 183
36
votes
6 answers
Reverse Chernoff bound
Is there an reverse Chernoff bound which bounds that the tail probability is at least so much.
i.e if $X_1,X_2,\ldots,X_n$ are independent binomial random variables and $\mu=\mathbb{E}[\sum_{i=1}^n X_i]$. Then can we prove $Pr[\sum_{i=1}^n X_i\geq…
Ashwinkumar B V
- 1,584
- 12
- 20