Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari
  • Member for 13 years, 8 months
  • 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
9k views

Open problems on the frontiers of TCS

38 votes
7 answers
3k views

What is the oldest open problem in TCS?

25 votes
1 answer
935 views

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

25 votes
2 answers
2k views

Formula size lower bounds for AC0 functions

23 votes
1 answer
1k views

Do all complexity classes have a leaf language characterization?

22 votes
2 answers
604 views

Lower bounds for constant-depth formulae?

21 votes
1 answer
809 views

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

21 votes
2 answers
918 views

Deterministic communication complexity vs partition number

20 votes
2 answers
957 views

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

19 votes
1 answer
1k 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
442 views

Characterization of read-once formulae over the full binary basis

15 votes
3 answers
433 views

Combinatorial characterization of exact learning with membership queries

14 votes
2 answers
506 views

Does L have a definition in terms of circuits?

13 votes
2 answers
880 views

Las Vegas vs Monte Carlo randomized decision tree complexity

10 votes
1 answer
370 views

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

10 votes
2 answers
876 views

Shortest formula for an n-term monotone CNF