User Karolina Sołtys

223

votes

60

answers

90k

views

Major unsolved problems in theoretical computer science?

big-list open-problem

Feb 10 at 13:30 Community♦ 1

145

votes

39

answers

41k

views

What videos should everybody watch?

soft-question big-list

Apr 5 at 1:36 Raphael Augusto 443

131

votes

29

answers

20k

views

Problems Between P and NPC

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

Aug 15 at 23:45 Mark S 802

83

votes

14

answers

17k

views

What kind of mathematical background is needed for complexity theory?

cc.complexity-theory soft-question advice-request

Nov 15 '15 at 17:26 Community♦ 1

67

votes

7

answers

4k

views

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

cc.complexity-theory lo.logic pl.programming-languages big-picture set-theory

Feb 20 '19 at 3:43 Timothy Chow 6,793

65

votes

11

answers

4k

views

What are good references to understanding the proof of the PCP theorem?

cc.complexity-theory reference-request pcp

Sep 21 '16 at 19:42 Sasho Nikolov 17.7k

61

votes

13

answers

8k

views

Open problems on the frontiers of TCS

big-list open-problem

Jun 4 at 2:45 Community♦ 1

54

votes

2

answers

3k

views

Can one amplify P=NP beyond P=PH?

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

May 18 '17 at 12:42 András Salamon 18.4k

51

votes

4

answers

3k

views

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

cc.complexity-theory space-bounded big-picture

Dec 2 '10 at 13:54 Michael Blondin 2,492

44

votes

5

answers

1k

views

Casual tours around proofs

soft-question big-list

Nov 11 '11 at 8:00 Kris 143

42

votes

4

answers

3k

views

Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

computability lo.logic proofs

Jul 18 '11 at 18:58 Community♦ 1

42

votes

4

answers

2k

views

Why have we not been able to develop a unified complexity theory of distributed computing?

big-picture dc.distributed-comp

Jun 14 '17 at 17:11 lamba 131

40

votes

3

answers

1k

views

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

cc.complexity-theory circuit-complexity upper-bounds

Oct 31 '10 at 19:07 Kristoffer Arnsfelt Hansen 3,915

39

votes

2

answers

938

views

How many distinct colors are needed to lower-bound the choosability of a graph?

graph-theory co.combinatorics graph-colouring exp-time-algorithms

Aug 10 '15 at 22:58 RJK 1,922

38

votes

13

answers

3k

views

Inspirational talk for final year high school pupils

soft-question teaching

Jun 15 '11 at 21:44 Community♦ 1

36

votes

2

answers

3k

views

Semantic vs. Syntactic Complexity Classes

cc.complexity-theory complexity-classes big-picture

Jan 10 '15 at 11:54 Community♦ 1

36

votes

13

answers

2k

views

Easy decision problem, hard search problem

cc.complexity-theory big-list

Oct 29 '13 at 15:01 Community♦ 1

35

votes

4

answers

1k

views

Interactive proofs for levels of the polynomial hierarchy

cc.complexity-theory interactive-proofs

Oct 27 '10 at 23:34 Community♦ 1

34

votes

17

answers

2k

views

Hardness jumps in computational complexity?

cc.complexity-theory

Jan 3 '19 at 18:34 Community♦ 1

33

votes

3

answers

2k

views

complexity of greatest common divisor (gcd)

cc.complexity-theory reference-request complexity-classes nt.number-theory

Jan 5 '15 at 16:24 SamiD 2,227

32

votes

1

answer

2k

views

Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?

cc.complexity-theory sat approximation-hardness

Sep 5 '11 at 19:17 Joe Fitzsimons 13.2k

32

votes

3

answers

2k

views

Is $AC^0/poly \cap NP$ contained in $P$?

cc.complexity-theory circuit-complexity uniformity

Apr 3 '17 at 17:01 Community♦ 1

32

votes

11

answers

2k

views

What is the quantum computational model?

quantum-computing big-picture

Jun 20 '11 at 9:49 Max 1,511

32

votes

4

answers

846

views

Hardness of approximation assuming NP != coNP

approximation-hardness conditional-results

Sep 9 '15 at 23:29 Abhinav 103

32

votes

3

answers

928

views

An Anthology of Complexity Assumptions

cc.complexity-theory complexity-classes big-list complexity-assumptions

Sep 1 '15 at 18:22 Community♦ 1

31

votes

1

answer

1k

views

Refereed games with uncorrelated semi-private coins

cc.complexity-theory gt.game-theory interactive-proofs

Jan 6 '11 at 14:46 Community♦ 1

29

votes

2

answers

903

views

Polynomial method for complexity results

cc.complexity-theory reference-request co.combinatorics polynomials

Nov 11 '10 at 13:20 Dana Moshkovitz 10.8k

29

votes

3

answers

3k

views

coNP certificate for Graph Isomorphism

cc.complexity-theory graph-isomorphism

Jan 5 '11 at 14:38 Francesco Cris 9

29

votes

7

answers

2k

views

Proving lower bounds by proving upper bounds

cc.complexity-theory lower-bounds

Dec 8 '10 at 5:15 Community♦ 1

29

votes

1

answer

1k

views

Are there canonical non-relativizing techniques?

cc.complexity-theory oracles relativization

Mar 16 '15 at 9:15 Jan Johannsen 4,459

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

64 Bookmarks

Major unsolved problems in theoretical computer science?

What videos should everybody watch?

Problems Between P and NPC

What kind of mathematical background is needed for complexity theory?

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

What are good references to understanding the proof of the PCP theorem?

Open problems on the frontiers of TCS

Can one amplify P=NP beyond P=PH?

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

Casual tours around proofs

Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

Why have we not been able to develop a unified complexity theory of distributed computing?

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

How many distinct colors are needed to lower-bound the choosability of a graph?

Inspirational talk for final year high school pupils

Semantic vs. Syntactic Complexity Classes

Easy decision problem, hard search problem

Interactive proofs for levels of the polynomial hierarchy

Hardness jumps in computational complexity?

complexity of greatest common divisor (gcd)

Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?

Is $AC^0/poly \cap NP$ contained in $P$?

What is the quantum computational model?

Hardness of approximation assuming NP != coNP

An Anthology of Complexity Assumptions

Refereed games with uncorrelated semi-private coins

Polynomial method for complexity results

coNP certificate for Graph Isomorphism

Proving lower bounds by proving upper bounds

Are there canonical non-relativizing techniques?