Theoretical Computer Science
Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari
  • Member for 13 years, 3 months
  • Last seen this week
Profile Activity

17 Questions

Score Activity Newest Views
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
927 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
603 views

Lower bounds for constant-depth formulae?

21 votes
1 answer
793 views

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

21 votes
2 answers
912 views

Deterministic communication complexity vs partition number

20 votes
2 answers
943 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
439 views

Characterization of read-once formulae over the full binary basis

15 votes
3 answers
423 views

Combinatorial characterization of exact learning with membership queries

14 votes
2 answers
501 views

Does L have a definition in terms of circuits?

13 votes
2 answers
875 views

Las Vegas vs Monte Carlo randomized decision tree complexity

10 votes
1 answer
359 views

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

10 votes
2 answers
862 views

Shortest formula for an n-term monotone CNF

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.