Skip to main content
Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari
  • Member for 13 years, 11 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
946 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
608 views

Lower bounds for constant-depth formulae?

21 votes
1 answer
816 views

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

21 votes
2 answers
923 views

Deterministic communication complexity vs partition number

20 votes
2 answers
964 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
449 views

Characterization of read-once formulae over the full binary basis

15 votes
3 answers
436 views

Combinatorial characterization of exact learning with membership queries

14 votes
2 answers
508 views

Does L have a definition in terms of circuits?

13 votes
2 answers
884 views

Las Vegas vs Monte Carlo randomized decision tree complexity

10 votes
1 answer
374 views

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

10 votes
2 answers
885 views

Shortest formula for an n-term monotone CNF