User Karolina Sołtys

44

votes

5

answers

1k

views

Casual tours around proofs

soft-question big-list

Nov 11 '11 at 8:00 Kris 143

20

votes

1

answer

567

views

FPT vs W[P] - Parameterized Complexity

cc.complexity-theory parameterized-complexity fixed-parameter-tractable

Apr 8 '15 at 15:34 Huck Bennett 4,422

24

votes

19

answers

3k

views

What tools do you use to give presentations?

soft-question research-practice writing

May 10 at 19:38 Denis 6,695

26

votes

5

answers

2k

views

Long-lasting errors in computer science

soft-question big-list

Aug 21 '11 at 8:26 Jukka Suomela 11.1k

134

votes

29

answers

21k

views

Problems Between P and NPC

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

Aug 15 at 23:45 Mark S 802

33

votes

3

answers

939

views

An Anthology of Complexity Assumptions

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

Sep 1 '15 at 18:22 Community♦ 1

10

votes

2

answers

432

views

Existence of $opt^c$-approximation of Dominating Set with $c < 1$?

cc.complexity-theory approximation-algorithms approximation-hardness

Mar 30 '11 at 6:17 Daniel Marx 1,948

27

votes

4

answers

1k

views

Compendium of the Best Approximation and Hardness Results for NP optimization problems

ds.algorithms reference-request approximation-algorithms approximation-hardness

Aug 25 '11 at 16:14 Randomizer 761

16

votes

2

answers

920

views

Collatz Conjecture & Grammars / Automata

fl.formal-languages nt.number-theory halting-problem

Nov 27 '13 at 2:16 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

23

votes

1

answer

870

views

Is there any justification to believe that $NL\neq L$?

cc.complexity-theory reference-request complexity-classes space-bounded

Mar 11 '11 at 22:56 Ryan Williams 25.7k

12

votes

1

answer

665

views

Improved lower bound on monotone circuit complexity of perfect matching?

cc.complexity-theory circuit-complexity matching

Jan 12 '11 at 16:01 V Vinay 3,783

15

votes

2

answers

968

views

Barriers and Monotone Circuit Complexity

cc.complexity-theory circuit-complexity barriers natural-proofs

Dec 18 '10 at 15:07 dick lipton 451

25

votes

3

answers

990

views

Reverse Graph Spectra Problem?

ds.algorithms graph-theory graph-algorithms spectral-graph-theory

Feb 13 '16 at 5:13 Jeffrey Shallit 6,818

3

votes

0

answers

240

views

Is there any research on the notion of weak isolation?

cc.complexity-theory randomness

Dec 11 '10 at 13:23 Hsien-Chih Chang 張顯之 7,438

26

votes

4

answers

943

views

What's the “smallest” complexity class for which a superlinear circuit bound is known?

cc.complexity-theory circuit-complexity

Oct 4 '17 at 2:22 Dmytro Taranovsky 2,092

21

votes

6

answers

1k

views

References on Circuit Lower Bounds

cc.complexity-theory lower-bounds circuit-complexity

Apr 15 '11 at 13:18 M.S. Dousti 16.1k

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

12

votes

1

answer

275

views

Explicit polynomials in 1 variable with superlogarithmic circuit complexity lower bounds?

cc.complexity-theory circuit-complexity polynomials algebraic-complexity

Nov 30 '10 at 14:13 Joshua Grochow 34.1k

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

30

votes

3

answers

3k

views

coNP certificate for Graph Isomorphism

cc.complexity-theory graph-isomorphism

Jan 5 '11 at 14:38 Francesco Cris 9

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

15

votes

0

answers

1k

views

Can a Penrose tile cellular automaton be Turing-complete?

computability machine-models cellular-automata

Nov 11 '10 at 22:18 Community♦ 1

6

votes

2

answers

378

views

PCPs with imperfect completeness

cc.complexity-theory reductions pcp

Nov 8 '10 at 20:49 Ramprasad 2,427

29

votes

2

answers

911

views

Polynomial method for complexity results

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

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

65

votes

11

answers

5k

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.8k

9

votes

2

answers

733

views

Quantum PCP and hardness of simulating of Hamiltonians

cc.complexity-theory quantum-computing approximation-hardness pcp physics

Oct 13 '13 at 0:46 Community♦ 1

22

votes

4

answers

1k

views

DNA-algorithms and NP-completeness

cc.complexity-theory np-hardness natural-computing tsp

Nov 7 '10 at 5:41 Kaveh 21k

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,267

23

votes

4

answers

1k

views

Social choice, arrow's theorem and open problems ?

Nov 30 '10 at 6:49 H. Reiju Mihara 71

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

64 Bookmarks

Casual tours around proofs

FPT vs W[P] - Parameterized Complexity

What tools do you use to give presentations?

Long-lasting errors in computer science

Problems Between P and NPC

An Anthology of Complexity Assumptions

Existence of $opt^c$-approximation of Dominating Set with $c < 1$?

Compendium of the Best Approximation and Hardness Results for NP optimization problems

Collatz Conjecture & Grammars / Automata

Can one amplify P=NP beyond P=PH?

Is there any justification to believe that $NL\neq L$?

Improved lower bound on monotone circuit complexity of perfect matching?

Barriers and Monotone Circuit Complexity

Reverse Graph Spectra Problem?

Is there any research on the notion of weak isolation?

What's the “smallest” complexity class for which a superlinear circuit bound is known?

References on Circuit Lower Bounds

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

Explicit polynomials in 1 variable with superlogarithmic circuit complexity lower bounds?

Proving lower bounds by proving upper bounds

coNP certificate for Graph Isomorphism

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

Can a Penrose tile cellular automaton be Turing-complete?

PCPs with imperfect completeness

Polynomial method for complexity results

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

Quantum PCP and hardness of simulating of Hamiltonians

DNA-algorithms and NP-completeness

complexity of greatest common divisor (gcd)

Social choice, arrow's theorem and open problems ?