Tsuyoshi Ito's user avatar
Tsuyoshi Ito's user avatar
Tsuyoshi Ito's user avatar
Tsuyoshi Ito
  • Member for 11 years, 11 months
  • Last seen more than 6 years ago
38 votes
Accepted

Why is Relativization a barrier?

25 votes
Accepted

Are there any problems that are easy to compute but hard to verify?

21 votes
Accepted

Finding interesting anagrams

15 votes
Accepted

NP completeness proof of a spanning tree problem

15 votes
Accepted

Is every linear-time algorithm a streaming algorithm?

13 votes
Accepted

How to scale down parallel complexity results to constantly many cores?

10 votes
Accepted

Are there complete problems for P and NP under other kinds of reductions?

9 votes
Accepted

Is finding dead-end nodes in NL?

8 votes
Accepted

Is an oracle ever useful if you can't control the input instances?

7 votes

What is the relationship between NP/NP-Complete/NP-Hard to time complexity?

7 votes

Minimize the maximum component of a sum of vectors

7 votes
Accepted

Is #P closed under exponentiation? modulo?

7 votes
Accepted

Complete Problems for $DSPACE(\log(n)^k)$

7 votes
Accepted

Polynomial time reductions

6 votes
Accepted

$L$ APX-hard thus PTAS for $L$ implies $\mathsf{P} = \mathsf{NP}$

6 votes

What is the decision version of independent set?

5 votes

Can one have a condition like this in semidefinite programming?

5 votes

Find $\epsilon'$ s.t $L_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon<\epsilon'$