user avatar
user avatar
user avatar
Pål GD
  • Member for 9 years, 10 months
  • Last seen more than a month ago
256 votes
11 answers
98k views

What is the enlightenment I'm supposed to attain after studying finite automata?

  • 5,165
152 votes
39 answers
45k views

What videos should everybody watch?

141 votes
30 answers
24k views

Problems Between P and NPC

  • 11.8k
62 votes
5 answers
4k views

Overarching reasons why problems are in P or BPP

61 votes
33 answers
4k views

Small steps for better TCS conferences?

55 votes
18 answers
14k views

Most memorable CS paper titles

  • 9,378
52 votes
4 answers
4k views

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

52 votes
11 answers
4k views

If you could rename dynamic programming...

  • 447
46 votes
4 answers
4k views

Generalized Ladner's Theorem

41 votes
7 answers
5k views

When does randomization speed up algorithms and it "shouldn't"?

35 votes
8 answers
11k views

Alan Turing's Contributions to Computer Science

  • 11.8k
31 votes
4 answers
4k views

Consequences of NP=PSPACE

  • 7,672
30 votes
2 answers
2k views

NP-intermediate problems with efficient quantum solutions

  • 4,493
28 votes
6 answers
1k views

Natural NP-complete problems with "large" witnesses

26 votes
3 answers
854 views

The complexity of determining if a fixed graph is a minor of another

25 votes
2 answers
1k views

Complexity zoo for unary languages

  • 4,721
25 votes
5 answers
2k views

Subexponentially solvable hard graph problems

25 votes
1 answer
898 views

Is it still open to determine the complexity of computing the treewidth of planar graphs?

  • 7,465
22 votes
5 answers
3k views

Program for computing Tree decomposition of a graph

21 votes
1 answer
1k views

What is the current known hardness of Graph Isomorphism?

  • 845
19 votes
3 answers
630 views

What separates easy global problems from hard global problems on graphs of bounded treewidth?

  • 3,160
19 votes
1 answer
433 views

Minor closed properties that are explicitly MSO expressible

18 votes
2 answers
599 views

Polynomial time solvable instances of Max-Sat

17 votes
2 answers
1k views

Comparing Two Algorithms for 3SUM problem over Integers

  • 1,996
17 votes
2 answers
1k views

Forbidden minors for bounded treewidth graphs

15 votes
5 answers
1k views

Hardness of FPT problems

  • 654
14 votes
1 answer
313 views

SERF-reducibility and subexponential algorithms

14 votes
9 answers
1k views

Counterintuitive results for undergraduates

  • 3,993
14 votes
1 answer
720 views

Second Smallest $s$-$t$-Cut in a Network

13 votes
1 answer
353 views

Does treewidth $k$ imply the existence of a $K_{1,k}$ minor?

  • 3,160