Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari
  • Member for 12 years, 1 month
  • Last seen this week
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

37 votes
7 answers
3k views

What is the oldest open problem in TCS?

25 votes
1 answer
903 views

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

25 votes
2 answers
2k views

Formula size lower bounds for AC0 functions

23 votes
1 answer
972 views

Do all complexity classes have a leaf language characterization?

22 votes
2 answers
577 views

Lower bounds for constant-depth formulae?

21 votes
1 answer
740 views

What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?

21 votes
2 answers
874 views

Deterministic communication complexity vs partition number

20 votes
2 answers
897 views

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

19 votes
1 answer
959 views

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

15 votes
1 answer
433 views

Characterization of read-once formulae over the full binary basis

15 votes
3 answers
395 views

Combinatorial characterization of exact learning with membership queries

13 votes
2 answers
845 views

Las Vegas vs Monte Carlo randomized decision tree complexity

13 votes
2 answers
483 views

Does L have a definition in terms of circuits?

10 votes
2 answers
793 views

Shortest formula for an n-term monotone CNF

10 votes
1 answer
335 views

A natural problem in $\textrm{S}_2^\textrm{P}$?