Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
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
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
939 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
605 views

Lower bounds for constant-depth formulae?

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?

21 votes
2 answers
922 views

Deterministic communication complexity vs partition number

20 votes
2 answers
961 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
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

14 votes
2 answers
508 views

Does L have a definition in terms of circuits?

13 votes
2 answers
882 views

Las Vegas vs Monte Carlo randomized decision tree complexity

10 votes
1 answer
371 views

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

10 votes
2 answers
884 views

Shortest formula for an n-term monotone CNF