Badge
| Nice Answer | Answer score of 10 or more. This badge can be awarded multiple times. |
Noam earned this badge 36 times |
dec 3 at 20:29
Unique SAT vs Exactly $m$ models
aug 17 at 10:52
Can addition be carried out in less than depth 5?
apr 13 '12 at 6:38
AM/MA and NP in analogy to P and BPP
mar 15 '12 at 23:16
Running a BPP algorithm with a half-random, half-adversarial string
sep 15 '11 at 2:27
What evidence is there that $coRP \neq NP$?
aug 24 '11 at 6:06
Parity-L vs. NL
aug 15 '11 at 3:44
Space-time tradeoff and the best algorithm
aug 11 '11 at 13:46
Shortest formula for an n-term monotone CNF
jul 7 '11 at 2:49
Inspirational talk for final year high school pupils
mar 10 '11 at 11:01
Does NP-hardness imply P-hardness?
jan 14 '11 at 1:22
Sum-of-square-roots-hard problems?
dec 21 '10 at 23:24
Communication Complexity …Classes?
nov 21 '10 at 0:03
Advice on good research practices
nov 18 '10 at 20:41
Are there known to exist functions with the following direct-sum property?
nov 2 '10 at 22:37
Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?
oct 27 '10 at 11:28
Interactive proofs for levels of the polynomial hierarchy
oct 25 '10 at 21:49
Inspirational talk for final year high school pupils
oct 21 '10 at 3:50
Is the convex combination of two potential games a potential game?
oct 21 '10 at 3:35
Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?
oct 16 '10 at 21:38
Does Nisan's pseudo-random generator relativize?
oct 16 '10 at 21:08
multi-party Communication complexity of “Set Partition problem”
oct 16 '10 at 16:25
How to get a job
oct 5 '10 at 15:26
Algorithmic game theory - nonstandard equilibrium concepts?
oct 4 '10 at 12:38
Algorithms from the Book.
oct 1 '10 at 18:17
Separating Logspace from Polynomial time
oct 1 '10 at 1:03
Simple question about decision problems
sep 25 '10 at 17:04
What are the consequences of Parity-L = P?
sep 12 '10 at 21:46
Evidence that PPAD is hard?
sep 3 '10 at 21:54
Computable function $f = \Theta(g)$ with $g$ uncomputable
aug 31 '10 at 8:54
Higher-order algorithms
aug 19 '10 at 19:19
For which algorithms is there a large gap between the theoretical analysis and reality?
aug 19 '10 at 15:39
Many-one reductions vs. Turing reductions to define NPC
