user avatar
user avatar
user avatar
Neal Young
  • Member for 10 years, 5 months
  • Last seen this week
120 votes
18 answers
9k views

Examples of the price of abstraction?

103 votes
39 answers
14k views

What are the recent TCS books whose drafts are available online?

  • 301
65 votes
5 answers
2k views

Problems that can be used to show polynomial-time hardness results

46 votes
0 answers
1k views

Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?

40 votes
10 answers
13k views

Data for testing graph algorithms

38 votes
9 answers
4k views

Optimal greedy algorithms for NP-hard problems

32 votes
0 answers
6k views

Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?

  • 6,605
30 votes
0 answers
740 views

The complexity of checking whether two DAG have the same number of topological sorts

  • 709
27 votes
0 answers
698 views

Is Hankelability NP-hard?

  • 3,920
26 votes
0 answers
607 views

Rank mod 6 vs rank over the reals

19 votes
2 answers
1k views

Can we decide whether a permanent has a unique term?

  • 13.5k
18 votes
1 answer
2k views

Complexity of interval cover problem

17 votes
0 answers
557 views

Sylver Coinage Game

16 votes
2 answers
541 views

Avalanche like stochastic process

  • 1,638
15 votes
0 answers
369 views

Complexity of approximating the range of a matrix

  • 3,920
14 votes
1 answer
399 views

Probability that a random sorting network works

14 votes
0 answers
471 views

Is it possible to find the median with a linear size sorting network?

  • 13.5k
14 votes
3 answers
523 views

Is this optimum travelling problem under deadlines NP-hard on trees?

  • 1,423
14 votes
1 answer
606 views

Exact Algorithm for edge labeling problem in DAG

  • 333
13 votes
1 answer
506 views

Comparing the Kolmogorov complexity of theories

12 votes
0 answers
358 views

How good is greedy in average?

  • 6,605
10 votes
2 answers
723 views

Set optimization problem - is it np-complete?

  • 101
9 votes
0 answers
152 views

Optimal bee swarm plots: NP-hard?

9 votes
2 answers
351 views

Bounds on this Strategy for Separating Words

8 votes
2 answers
265 views

Cheap online selection with weighted comparisons

  • 664
8 votes
0 answers
140 views

Determining if transducer automaton has two states with intersecting images, without minimizing?

  • 181
8 votes
3 answers
852 views

Is this vertex ordering optimization NP-Hard?

  • 533
7 votes
1 answer
2k views

Test set and benchmarks for linear programming

  • 1,145
6 votes
1 answer
371 views

Complexity of finding the largest induced subgraph with all even degrees

6 votes
2 answers
340 views

Infinite process balls in bins problem

  • 201