user avatar
user avatar
user avatar
Robin Kothari
  • Member for 12 years
  • Last seen this week
480 votes
72 answers
178k views

What papers should everyone read?

141 votes
30 answers
24k views

Problems Between P and NPC

  • 11.8k
82 votes
20 answers
10k views

Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?

70 votes
7 answers
4k views

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

65 votes
5 answers
2k views

Problems that can be used to show polynomial-time hardness results

62 votes
13 answers
8k views

Open problems on the frontiers of TCS

57 votes
16 answers
4k views

What tools do you use to write papers?

  • 436
45 votes
5 answers
1k views

Casual tours around proofs

41 votes
9 answers
5k views

References for TCS proof techniques

  • 839
28 votes
2 answers
960 views

Approximate counting problem capturing BQP

  • 7,509
25 votes
6 answers
2k views

Graph families which have polynomial time algorithms for computing the chromatic number

24 votes
3 answers
918 views

Can we quantify the "degree of quantumness" in a quantum algorithm ?

20 votes
2 answers
892 views

Problems between NC and P: How many have been resolved from this list?

13 votes
1 answer
676 views

Circuits with oracles vs. Turing Machines with oracles