User Robin Kothari - Theoretical Computer Science Stack Exchange

As of May 31, 2023, we have updated our Code of Conduct.

Robin Kothari

Member for 12 years, 9 months
Last seen this week

8 Offered bounties for 600 reputation

Active Offered Earned

15 votes

1 answer

469 views

+50

Information complexity of query algorithms?

asked Apr 3, 2015 at 21:45

17 votes

1 answer

795 views

+50

Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?

asked Feb 15, 2013 at 21:18

27 votes

5 answers

933 views

+50

Quantum proofs of classical theorems

asked Oct 9, 2011 at 22:48

21 votes

2 answers

1k views

+50

Can addition be carried out in less than depth 5?

asked Jul 30, 2012 at 17:27

19 votes

1 answer

981 views

+200

Most efficient way to convert an $\text{AC}^0$ circuit to a circuit (of any depth) with gate fanout 1

asked Aug 8, 2011 at 23:11

18 votes

1 answer

539 views

+100

Using the extra power of the negative adversary method

asked Jul 14, 2011 at 13:36

29 votes

0 answers

1k views

+50

Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?

asked Aug 23, 2010 at 20:21

65 votes

5 answers

2k views

+50

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

asked Sep 14, 2010 at 2:56