user avatar
user avatar
user avatar
Michaël Cadilhac
  • Member for 11 years, 10 months
  • Last seen this week
480 votes
72 answers
177k views

What papers should everyone read?

268 votes
39 answers
135k views

What Books Should Everyone Read?

  • 16.3k
151 votes
39 answers
45k views

What videos should everybody watch?

141 votes
30 answers
24k views

Problems Between P and NPC

  • 11.8k
93 votes
9 answers
18k views

What would it mean to disprove Church-Turing thesis?

82 votes
20 answers
10k views

Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?

80 votes
5 answers
4k views

Techniques for Reversing the Order of Quantifiers

  • 16.3k
56 votes
7 answers
4k views

For which problems in P is it easier to verify the result than to find it?

55 votes
2 answers
4k views

Can one amplify P=NP beyond P=PH?

52 votes
4 answers
4k views

Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

51 votes
4 answers
5k views

What are the best current lower bounds on 3SAT?

46 votes
4 answers
4k views

Generalized Ladner's Theorem

46 votes
5 answers
3k views

Positive topological ordering

41 votes
2 answers
2k views

Are the problems PRIMES, FACTORING known to be P-hard?

  • 411
41 votes
3 answers
1k views

A fixed-depth characterization of $TC^0$? $NC^1$?

39 votes
5 answers
1k views

Is there a logic without induction that captures much of P?

37 votes
3 answers
2k views

Parameterized complexity of Hitting Set in finite VC-dimension

  • 2,583
32 votes
2 answers
2k views

How difficult is it to use the Mulmuley-Sohoni GCT approach to show *known* complexity separations?

25 votes
4 answers
2k views

Separating Logspace from Polynomial time

25 votes
2 answers
2k views

Formula size lower bounds for AC0 functions

22 votes
2 answers
575 views

Lower bounds for constant-depth formulae?

22 votes
3 answers
1k views

Problems outside of P that are not P-hard

21 votes
1 answer
505 views

For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

  • 2,789
21 votes
4 answers
489 views

Which results in complexity theory make essential use of uniformity?

  • 21.3k
21 votes
3 answers
961 views

Limits to Parallel Computing

20 votes
0 answers
499 views

Model-checking for three-variable logics and restricted structures

20 votes
3 answers
740 views

Is it hard to find optimal addition chains?

  • 22.8k
19 votes
1 answer
950 views

Most efficient way to convert an $\text{AC}^0$ circuit to a circuit (of any depth) with gate fanout 1

18 votes
0 answers
509 views

Are monotone Boolean functions in P well-approximated by monotone polynomial-size circuits?

  • 5,983
17 votes
0 answers
487 views

What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?