User Neal Young

18 answers

120 votes

9k views

63 bookmarks

Examples of the price of abstraction?

Aug 26 '10 at 4:00

39 answers

103 votes

14k views

142 bookmarks

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

reference-request big-list books

Dec 5 '10 at 2:01

5 answers

65 votes

2k views

28 bookmarks

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

cc.complexity-theory lower-bounds conditional-results

Sep 14 '10 at 2:56

0 answers

46 votes

1k views

12 bookmarks

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

cc.complexity-theory sat planar-graphs succinct

Jan 19 '13 at 16:24

10 answers

40 votes

13k views

20 bookmarks

Data for testing graph algorithms

ds.algorithms graph-theory ds.data-structures data-sets

Aug 29 '10 at 14:02

9 answers

38 votes

4k views

14 bookmarks

Optimal greedy algorithms for NP-hard problems

cc.complexity-theory lower-bounds approximation-algorithms greedy-algorithms approximation-hardness

Sep 13 '10 at 2:01

0 answers

32 votes

5k views

11 bookmarks

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

graph-theory lower-bounds directed-acyclic-graph dynamic-programming shortest-path

Dec 3 '12 at 15:49

0 answers

30 votes

731 views

6 bookmarks

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

cc.complexity-theory complexity-classes counting-complexity open-problem partial-order

Nov 17 '10 at 22:21

0 answers

27 votes

689 views

5 bookmarks

Is Hankelability NP-hard?

cc.complexity-theory

Apr 16 '15 at 17:44

0 answers

26 votes

592 views

3 bookmarks

Rank mod 6 vs rank over the reals

linear-algebra matrices boolean-matrix

Jun 7 '17 at 16:57

2 answers

19 votes

1k views

9 bookmarks

Can we decide whether a permanent has a unique term?

cc.complexity-theory ds.algorithms matrices matching permanent

Oct 8 '10 at 8:17

1 answers

18 votes

2k views

4 bookmarks

Complexity of interval cover problem

cc.complexity-theory np-hardness

May 6 '13 at 12:39

2 answers

16 votes

538 views

7 bookmarks

Avalanche like stochastic process

pr.probability markov-chains stochastic-process

Nov 7 '10 at 17:49

0 answers

16 votes

554 views

4 bookmarks

Sylver Coinage Game

co.combinatorics combinatorial-game-theory

Apr 14 '14 at 11:03

0 answers

15 votes

365 views

4 bookmarks

Complexity of approximating the range of a matrix

cc.complexity-theory approximation-algorithms linear-algebra

Jan 28 '16 at 10:00

1 answers

14 votes

397 views

2 bookmarks

Probability that a random sorting network works

sorting-network

Feb 28 '18 at 16:47

1 answers

14 votes

501 views

4 bookmarks

Comparing the Kolmogorov complexity of theories

lo.logic kolmogorov-complexity

Feb 3 '15 at 4:15

1 answers

14 votes

603 views

1 bookmarks

Exact Algorithm for edge labeling problem in DAG

ds.algorithms reference-request co.combinatorics graph-algorithms directed-acyclic-graph

Jan 31 '12 at 15:55

3 answers

14 votes

522 views

4 bookmarks

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

ds.algorithms graph-algorithms np-hardness

Feb 7 '12 at 17:40

0 answers

14 votes

458 views

5 bookmarks

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

ds.algorithms sorting sorting-network selection

Dec 9 '14 at 14:40

0 answers

12 votes

357 views

2 bookmarks

How good is greedy in average?

cc.complexity-theory co.combinatorics approximation-algorithms optimization greedy-algorithms

May 17 '15 at 20:58

2 answers

10 votes

718 views

2 bookmarks

Set optimization problem - is it np-complete?

np-hardness optimization

Jan 12 '12 at 20:12

0 answers

9 votes

150 views

3 bookmarks

Optimal bee swarm plots: NP-hard?

np-hardness cg.comp-geom

Oct 27 '19 at 11:52

2 answers

9 votes

344 views

3 bookmarks

Bounds on this Strategy for Separating Words

automata-theory dfa

Jul 28 '20 at 16:25

3 answers

8 votes

806 views

7 bookmarks

Is this vertex ordering optimization NP-Hard?

graph-theory np-hardness permutations

May 22 '17 at 12:54

0 answers

8 votes

136 views

2 bookmarks

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

automata-theory minimization

Jun 4 '20 at 10:06

2 answers

8 votes

265 views

2 bookmarks

Cheap online selection with weighted comparisons

cc.complexity-theory ds.algorithms reference-request online-algorithms

Aug 8 '12 at 12:05

1 answers

7 votes

1k views

2 bookmarks

Test set and benchmarks for linear programming

reference-request linear-programming

Mar 16 '13 at 20:35

2 answers

6 votes

329 views

3 bookmarks

Infinite process balls in bins problem

pr.probability

Feb 7 '19 at 17:17

1 answers

6 votes

362 views

1 bookmarks

Complexity of finding the largest induced subgraph with all even degrees

graph-theory graph-algorithms np-complete

Nov 18 '19 at 20:23

Stack Exchange Network

current community

your communities

more stack exchange communities

60 Bookmarks