Tsuyoshi Ito

Princeton, NJ

nec-labs.com/~tsuyoshi

Age: 33

I am a researcher in theoretical computer science working on quantum computing.

top accounts reputation activity favorites subscriptions

Why is “cannot” spelled as one word?

orthography modal-verbs negation asked Oct 29 '10 at 1:37

english.stackexchange.com

29 votes

Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?

cc.complexity-theory sat approximation-hardness asked Sep 26 '10 at 18:04

cstheory.stackexchange.com

26 votes

A decision problem which is not known to be in PH but will be in P if P=NP

cc.complexity-theory conditional-results np polynomial-hierarchy asked Oct 8 '10 at 17:17

cstheory.stackexchange.com

20 votes

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

cc.complexity-theory approximation-hardness unique-games-conjecture asked Jun 10 '12 at 15:23

cstheory.stackexchange.com

19 votes

On existence of an integer between $\sqrt{n}$ and $\sqrt{2n}$ coprime to $n$

number-theory analytic-number-theory asked Mar 5 '11 at 2:26

math.stackexchange.com

17 votes

Computational complexity of the 3-partition problem with distinct numbers

cc.complexity-theory np-hardness asked Aug 28 '10 at 21:30

cstheory.stackexchange.com

14 votes

Deciding whether an NC${}^0_3$ circuit computes a permutation or not

cc.complexity-theory permutations circuit-families asked Aug 19 '12 at 20:41

cstheory.stackexchange.com

14 votes

Is there an easily accessible list of terms in the Japanese grammar written both in Japanese and English?

translation resources terminology asked May 31 '11 at 19:00

japanese.stackexchange.com

12 votes

Is it correct to say “He got a fatal injury in the accident” when there is a possibility that the person’s life will be saved?

meaning vocabulary word-usage asked Aug 21 '11 at 22:15

english.stackexchange.com

11 votes

Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$

cc.complexity-theory oracles relativization polynomial-hierarchy separation asked Nov 16 '11 at 19:15

cstheory.stackexchange.com

Top Answers

How important is knowing how to program for TCS?

cstheory.stackexchange.com

Is it acceptable to extend results from an arXiv paper that has not appeared in a journal?

academia.stackexchange.com

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

cstheory.stackexchange.com

Verifying unique solutions of SAT

cstheory.stackexchange.com

Consequences of #P = FP

cstheory.stackexchange.com

Did ありがとう come from Portuguese “obrigado”?

japanese.stackexchange.com

Conditions for NFA universality

cstheory.stackexchange.com

How can I differentiate between feet and legs?

japanese.stackexchange.com

If an insertion in parentheses ends with a smiley, how do I distinguish between the two?

english.stackexchange.com

$\ell_p$-norm preserving Turing machines

cstheory.stackexchange.com

Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

cstheory.stackexchange.com

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

cstheory.stackexchange.com

What are regular expressions good for?

cstheory.stackexchange.com

Using more than one の

japanese.stackexchange.com

“log in to” or “log into” or “login to”

english.stackexchange.com

Japanese people hate my site

ux.stackexchange.com

Hardness of approximation - additive error

cstheory.stackexchange.com

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

cstheory.stackexchange.com

Use of 厨 on the Internet

japanese.stackexchange.com

How do I politely ask my boss for a moment of his time?

japanese.stackexchange.com

How is アェ pronounced?

japanese.stackexchange.com

Should I use “everyone's”, “everyones'” or “everyones”?

english.stackexchange.com

Why is Relativization a barrier?

cs.stackexchange.com

Is the following problem NP-Hard?

cstheory.stackexchange.com

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

cstheory.stackexchange.com

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

cstheory.stackexchange.com

Graphs in which all shortest paths are unique

cstheory.stackexchange.com

What is the difference between tori vs. dori?

japanese.stackexchange.com

Temperature abbreviations?

japanese.stackexchange.com

Why is the Japanese government considering adding kanji such as “cancer” to the jinmeiyō kanji?

japanese.stackexchange.com