Tsuyoshi Ito

less info

9,760 reputation

22161

bio	website	cs.uwaterloo.ca/~tito
	location	Princeton, NJ
	age	32
visits	member for	1 year, 8 months
	seen	15 mins ago
stats	profile views	2,254

I am a research staff member working on quantum computing at the NEC Laboratories America, Inc., Princeton. But my posts on Stack Exchange are personal and not related to my employer.

A mathematician is said to be pure if he/she cannot be written as a convex combination of two mathematicians other than him/herself.

	9,760 reputation	bio	website	cs.uwaterloo.ca/~tito	visits	member for	1 year, 8 months
22161 badges		location	Princeton, NJ		seen	15 mins ago

summary answers questions tags badges favorites bounties reputation activity

92 Answers

votes activity newest

39	How important is knowing how to program for TCS?
22	Consequences of #P = FP
21	Deciding if a given $\mathsf{NC}^0$ circuit computes a permutation
20	Conditions for NFA universality
19	Verifying unique solutions of SAT

9,760 Reputation

top 2% overall

+10	Conditions for NFA universality
+10	Is finding the minimum regular expression an NP-complete problem?
+95	Techniques for proving NP completeness for a specific sequence of instances
+5	A decision problem which is not known to be in PH but will be in P if P=NP

6 Questions

votes activity newest

27	Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?
26	A decision problem which is not known to be in PH but will be in P if P=NP
17	Computational complexity of the 3-partition problem with distinct numbers
11	Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$
10	Gap hardness of Multi-Dimensional Cover

100 Tags

457 cc.complexity-theory × 54	72 reference-request × 8
176 ds.algorithms × 22	71 soft-question × 4
154 complexity-classes × 16	59 graph-theory × 8
141 np-hardness × 14	57 co.combinatorics × 9
79 counting-complexity × 7	56 fl.formal-languages × 5

14 Accounts

	Japanese Language and Usage	12,600 rep	11846
	Theoretical Computer Science	9,760 rep	22161
	English Language and Usage	2,157 rep	719
$Mathematics$	Mathematics	1,337 rep	315
	Stack Overflow	770 rep	28