Badge
| Nice Answer | Answer score of 10 or more. This badge can be awarded multiple times. |
Tsuyoshi Ito earned this badge 45 times |
feb 18 at 22:53
Are vertex colourings--in a sense--edge colourings?
feb 5 at 6:08
Graphs in which all shortest paths are unique
oct 27 at 23:48
Name for terminals on the left-hand side of grammar rules?
sep 25 at 0:50
One-sided errors in probablistic proof systems
sep 22 at 5:28
$\mathcal{MA}$ in terms of $\mathcal{PCP}$
jun 11 '12 at 8:36
What is UG-hardness, and how is it different from NP-hardness based on the unique games conjecture?
jun 9 '12 at 9:31
A promise problem to decide whether two given pure quantum states are close or far apart
may 14 '12 at 1:42
Is finding the minimum regular expression an NP-complete problem?
apr 23 '12 at 16:35
What classes of mathematical programs can be solved exactly or approximately, in polynomial time?
nov 28 '11 at 15:47
What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs?
nov 26 '11 at 20:29
Best way to determine the minimum dimension of a structure given only distances between points
nov 8 '11 at 7:05
How important is knowing how to program for TCS?
oct 23 '11 at 4:46
Deciding if a given $\mathsf{NC}^0$ circuit computes a permutation
aug 31 '11 at 20:04
Does there exist a complexity class such that the number of accepting paths is a prime number?
jul 23 '11 at 9:42
Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?
jul 22 '11 at 10:36
Can you decide equivalence for monotone Boolean expressions that do not contain negation in PTIME?
jul 21 '11 at 16:35
What are regular expressions good for?
jul 15 '11 at 13:19
$\ell_p$-norm preserving Turing machines
jul 11 '11 at 14:26
Does the trace norm of the difference of two density matrices being one imply these two density matrices can be simultaneously diagonalizable?
jul 7 '11 at 2:49
Is the “Fewest Discriminating Bits” problem NP-complete?
may 29 '11 at 21:16
How do you get a “Physical Intuition” for results in TCS?
may 2 '11 at 4:42
Solvability of matrix filling
apr 5 '11 at 2:00
Complexity of Turing self-reducibility of Clique problem?
mar 20 '11 at 12:35
NP-hardness of a special case of Number Partitioning
mar 13 '11 at 23:01
What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?
dec 17 '10 at 23:24
Is there a candidate for a natural problem in $P/poly - P$?
dec 17 '10 at 23:19
Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?
dec 17 '10 at 23:14
“Caged” complexity classes ?
dec 11 '10 at 21:16
A Multi-cut Problem
dec 11 '10 at 6:00
Can a probabilistic Turing machine solve the halting problem?
dec 6 '10 at 14:14
Complexity of finding a second solution given a correct solution to an NP-complete problem
dec 4 '10 at 17:32
Conditions for NFA universality
nov 23 '10 at 8:50
Are there languages that are not in RE nor CO-RE?
nov 10 '10 at 19:54
Is the following problem NP-Hard?
oct 30 '10 at 5:45
Complexity of exponential function
oct 24 '10 at 14:10
Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?
oct 24 '10 at 10:27
Hardness of approximation - additive error
oct 8 '10 at 15:56
Consequences of #P = FP
sep 27 '10 at 11:22
Verifying unique solutions of SAT
aug 30 '10 at 20:59
Cutting-sticks puzzle
