Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari
  • Member for 13 years, 9 months
  • Last seen this week
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?

65 votes
5 answers
2k views

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

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?

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

20 votes
2 answers
962 views

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

25 votes
1 answer
940 views

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

21 votes
2 answers
922 views

Deterministic communication complexity vs partition number

10 votes
2 answers
884 views

Shortest formula for an n-term monotone CNF

13 votes
2 answers
882 views

Las Vegas vs Monte Carlo randomized decision tree complexity

21 votes
1 answer
813 views

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

22 votes
2 answers
606 views

Lower bounds for constant-depth formulae?

14 votes
2 answers
508 views

Does L have a definition in terms of circuits?

15 votes
1 answer
444 views

Characterization of read-once formulae over the full binary basis

15 votes
3 answers
434 views

Combinatorial characterization of exact learning with membership queries

10 votes
1 answer
371 views

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