User Michaël Cadilhac

480 votes

72 answers

177k views

What papers should everyone read?

big-list soft-question

Ryan Williams

26.4k

asked Sep 12, 2010 at 0:43

268 votes

39 answers

135k views

What Books Should Everyone Read?

M.S. Dousti

16.3k

asked Nov 22, 2010 at 15:00

151 votes

39 answers

45k views

What videos should everybody watch?

soft-question big-list

Aaron Sterling

6,954

asked Sep 12, 2010 at 17:04

141 votes

30 answers

24k views

Problems Between P and NPC

cc.complexity-theory np-hardness big-list np-intermediate

Lev Reyzin♦

11.8k

asked Aug 17, 2010 at 2:07

93 votes

9 answers

18k views

What would it mean to disprove Church-Turing thesis?

computability proofs hypercomputation

user200

asked Aug 17, 2010 at 2:48

82 votes

20 answers

10k views

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

reference-request soft-question big-list topology

Derrick Stolee

2,004

asked Oct 4, 2010 at 18:50

80 votes

5 answers

4k views

Techniques for Reversing the Order of Quantiﬁers

lo.logic big-picture proof-techniques

M.S. Dousti

16.3k

asked Jan 21, 2011 at 22:58

56 votes

7 answers

4k views

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

cc.complexity-theory ds.algorithms reference-request

Andras Farago

10.7k

asked Oct 31, 2015 at 14:56

55 votes

2 answers

4k views

Can one amplify P=NP beyond P=PH?

cc.complexity-theory reference-request complexity-classes conditional-results polynomial-hierarchy

András Salamon

18.7k

asked Mar 13, 2011 at 16:55

52 votes

4 answers

4k views

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

cc.complexity-theory space-bounded big-picture

Hsien-Chih Chang 張顯之

7,578

asked Dec 1, 2010 at 18:20

51 votes

4 answers

5k views

What are the best current lower bounds on 3SAT?

cc.complexity-theory lower-bounds sat

Joe Fitzsimons

13.4k

asked Aug 17, 2010 at 3:06

46 votes

4 answers

4k views

Generalized Ladner's Theorem

cc.complexity-theory reference-request np-intermediate

András Salamon

18.7k

asked Aug 31, 2010 at 14:52

46 votes

5 answers

3k views

Positive topological ordering

ds.algorithms directed-acyclic-graph partial-order topological-sorting

David Eppstein

50.2k

asked Sep 16, 2010 at 1:24

41 votes

2 answers

2k views

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

cc.complexity-theory lower-bounds factoring primes p-hardness

k m

411

asked Aug 29, 2011 at 0:56

41 votes

3 answers

1k views

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

cc.complexity-theory circuit-complexity upper-bounds

Ryan Williams

26.4k

asked Oct 21, 2010 at 1:18

39 votes

5 answers

1k views

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

cc.complexity-theory lo.logic descriptive-complexity finite-model-theory

András Salamon

18.7k

asked Sep 2, 2010 at 11:25

37 votes

3 answers

2k views

Parameterized complexity of Hitting Set in finite VC-dimension

cc.complexity-theory cg.comp-geom set-cover parameterized-complexity vc-dimension

James King

2,583

asked Aug 17, 2010 at 17:48

32 votes

2 answers

2k views

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

cc.complexity-theory gct

Mugizi Rwebangira

1,278

asked Sep 4, 2010 at 12:00

25 votes

4 answers

2k views

Separating Logspace from Polynomial time

cc.complexity-theory lower-bounds space-bounded

Shiva Kintali

10.5k

asked Sep 29, 2010 at 7:39

25 votes

2 answers

2k views

Formula size lower bounds for AC0 functions

cc.complexity-theory lower-bounds circuit-complexity formulas

Robin Kothari

13.3k

asked Jun 28, 2011 at 22:59

22 votes

2 answers

575 views

Lower bounds for constant-depth formulae?

cc.complexity-theory circuit-complexity lower-bounds

Robin Kothari

13.3k

asked Aug 17, 2010 at 5:34

22 votes

3 answers

1k views

Problems outside of P that are not P-hard

cc.complexity-theory complexity-classes

Artem Kaznatcheev♦

10.1k

asked Sep 1, 2011 at 6:30

21 votes

1 answer

505 views

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

cc.complexity-theory automata-theory regular-expressions pspace

mikero

2,789

asked May 12, 2016 at 1:39

21 votes

4 answers

489 views

Which results in complexity theory make essential use of uniformity?

cc.complexity-theory

Kaveh

21.3k

asked Aug 17, 2010 at 2:09

21 votes

3 answers

961 views

Limits to Parallel Computing

cc.complexity-theory complexity-classes big-picture

Vladimir Levin

211

asked Oct 8, 2010 at 2:35

20 votes

0 answers

499 views

Model-checking for three-variable logics and restricted structures

cc.complexity-theory co.combinatorics lo.logic descriptive-complexity

András Salamon

18.7k

asked Nov 3, 2010 at 18:47

20 votes

3 answers

740 views

Is it hard to find optimal addition chains?

reference-request np-hardness

Jeffε

22.8k

asked Sep 3, 2010 at 15:49

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

cc.complexity-theory lower-bounds circuit-complexity

Robin Kothari

13.3k

asked Aug 8, 2011 at 23:11

18 votes

0 answers

509 views

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

cc.complexity-theory circuit-complexity pr.probability

Gil Kalai

5,983

asked May 13, 2015 at 6:58

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}$?

cc.complexity-theory complexity-classes circuit-complexity advice-and-nonuniformity logspace

Damiano Mazza

4,823

asked Oct 9, 2014 at 10:14

Stack Exchange Network

current community

your communities

more stack exchange communities

48 Bookmarks

What papers should everyone read?

What Books Should Everyone Read?

What videos should everybody watch?

Problems Between P and NPC

What would it mean to disprove Church-Turing thesis?

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

Techniques for Reversing the Order of Quantiﬁers

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

Can one amplify P=NP beyond P=PH?

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

What are the best current lower bounds on 3SAT?

Generalized Ladner's Theorem

Positive topological ordering

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

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

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

Parameterized complexity of Hitting Set in finite VC-dimension

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

Separating Logspace from Polynomial time

Formula size lower bounds for AC0 functions

Lower bounds for constant-depth formulae?

Problems outside of P that are not P-hard

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

Which results in complexity theory make essential use of uniformity?

Limits to Parallel Computing

Model-checking for three-variable logics and restricted structures

Is it hard to find optimal addition chains?

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

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

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