Robin Kothari

Member for 13 years, 1 month
Last seen this week

Summary

Reputation

13,487

13.5k
13.1k
12.7k

2020
2021
2022
2023

Next tag badge

complexity-classes

192/100 score

16/20 answers

Badges

2

60

115

Newest

Good Answer

Next badge

0/1

Excavator

Answers

View all 108 answers

Score Activity Newest

52

What papers should everyone read?

Sep 12, 2010

40

Do any quantum algorithms improve on classical SAT?

Aug 17, 2016

33

Semantic vs. Syntactic Complexity Classes

Sep 13, 2010

32

Funny TCS-related papers etc?

Nov 18, 2010

32

What are the recent TCS books whose drafts are available online?

Dec 5, 2010

Questions

View all 17 questions

Score Activity Newest Views

65

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

Sep 14, 2010

62

Open problems on the frontiers of TCS

Sep 6, 2010

38

What is the oldest open problem in TCS?

Oct 3, 2010

25

Approximate degree of $\textrm{AC}^0$

Jul 18, 2012

25

Formula size lower bounds for AC0 functions

Jun 28, 2011

Tags

View all 83 tags

cc.complexity-theory

688

Score

77

posts

quantum-computing

227

Score

23

posts

complexity-classes

194

Score

19

posts

circuit-complexity

155

Score

18

posts

reference-request

123

Score

22

posts

Reputation

+10

What is the big version of NC?

+10

Does L have a definition in terms of circuits?

+10

Is relativization well-defined?

+10

Parity and circuit complexity

Badges

View all badges

2

gold badges

Electorate

May 28, 2012
Fanatic

Nov 24, 2010

60

silver badges

Sportsmanship

Jan 25, 2011
Convention

Dec 11, 2010
Beta

Sep 10, 2010

115

bronze badges

quantum-computing

Aug 18, 2016
Altruist

Aug 17, 2012
cc.complexity-theory

Dec 3, 2010

Accounts

View all 14 accounts

Theoretical Computer Science

13.5k
2
60
115

1,282
9
16

553
1
4
7

German Language

388
2
7

273
1
2
8

Active bounties (0)

Active Offered Earned

This user has no active bounties

Votes cast

2,548

upvotes

197

downvotes

1,219

question votes

1,526

answer votes

2

this month