user avatar
user avatar
user avatar
Tsuyoshi Ito
  • Member for 11 years, 11 months
  • Last seen more than 4 years ago
  • Tokyo, Japan
60 votes

How important is knowing how to program for TCS?

29 votes
Accepted

Deciding if a given $\mathsf{NC}^0$ circuit computes a permutation

28 votes

Verifying unique solutions of SAT

25 votes
Accepted

Consequences of #P = FP

25 votes
Accepted

Graphs in which all shortest paths are unique

24 votes
Accepted

Hardness of approximation - additive error

23 votes
Accepted

What are regular expressions good for?

22 votes
Accepted

Conditions for NFA universality

21 votes
Accepted

$\ell_p$-norm preserving Turing machines

20 votes
Accepted

Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

20 votes
Accepted

Do there exist x such that K(xx)<K(x), where K is Kolmogorov complextity.

19 votes
Accepted

$\mathcal{MA}$ in terms of $\mathcal{PCP}$

18 votes
Accepted

Two matrices related by a permutation $B = P A P^T$ - complexity

18 votes

What classes of mathematical programs can be solved exactly or approximately, in polynomial time?

17 votes
Accepted

Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?

17 votes

Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?

17 votes

Complexity of exponential function

17 votes
Accepted

What is UG-hardness, and how is it different from NP-hardness based on the unique games conjecture?

16 votes
Accepted

Cutting-sticks puzzle

16 votes

How do you get a "Physical Intuition" for results in TCS?

16 votes

What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?

16 votes
Accepted

Is the following problem NP-Hard?

15 votes

Complexity of finding a second solution given a correct solution to an NP-complete problem

15 votes
Accepted

Can strong NP-hardness really be shown using plain polytime reductions?

15 votes
Accepted

Probability of generating a desired permutation by random swaps

14 votes

Are vertex colourings--in a sense--edge colourings?

14 votes
Accepted

Consensus on P = NP in a world where RP = NP

14 votes
Accepted

Are there non-closed complexity classes for which there are complete problems?

14 votes
Accepted

similar matrices

14 votes

Best way to determine the minimum dimension of a structure given only distances between points

1
2 3 4 5