Neal Young
  • Member for 9 years, 11 months
  • Last seen this week
18 answers
120 votes
9k views
63 bookmarks
Examples of the price of abstraction?
39 answers
103 votes
14k views
142 bookmarks
What are the recent TCS books whose drafts are available online?
5 answers
65 votes
2k views
28 bookmarks
Problems that can be used to show polynomial-time hardness results
0 answers
46 votes
1k views
12 bookmarks
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
10 answers
40 votes
13k views
20 bookmarks
Data for testing graph algorithms
9 answers
38 votes
4k views
14 bookmarks
Optimal greedy algorithms for NP-hard problems
0 answers
32 votes
5k views
11 bookmarks
Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?
0 answers
30 votes
731 views
6 bookmarks
The complexity of checking whether two DAG have the same number of topological sorts
0 answers
27 votes
689 views
5 bookmarks
Is Hankelability NP-hard?
0 answers
26 votes
592 views
3 bookmarks
Rank mod 6 vs rank over the reals
2 answers
19 votes
1k views
9 bookmarks
Can we decide whether a permanent has a unique term?
1 answers
18 votes
2k views
4 bookmarks
Complexity of interval cover problem
2 answers
16 votes
538 views
7 bookmarks
Avalanche like stochastic process
0 answers
16 votes
554 views
4 bookmarks
Sylver Coinage Game
0 answers
15 votes
365 views
4 bookmarks
Complexity of approximating the range of a matrix
1 answers
14 votes
397 views
2 bookmarks
Probability that a random sorting network works
1 answers
14 votes
501 views
4 bookmarks
Comparing the Kolmogorov complexity of theories
1 answers
14 votes
603 views
1 bookmarks
Exact Algorithm for edge labeling problem in DAG
3 answers
14 votes
522 views
4 bookmarks
Is this optimum travelling problem under deadlines NP-hard on trees?
0 answers
14 votes
458 views
5 bookmarks
Is it possible to find the median with a linear size sorting network?
0 answers
12 votes
357 views
2 bookmarks
How good is greedy in average?
2 answers
10 votes
718 views
2 bookmarks
Set optimization problem - is it np-complete?
0 answers
9 votes
150 views
3 bookmarks
Optimal bee swarm plots: NP-hard?
2 answers
9 votes
344 views
3 bookmarks
Bounds on this Strategy for Separating Words
3 answers
8 votes
806 views
7 bookmarks
Is this vertex ordering optimization NP-Hard?
0 answers
8 votes
136 views
2 bookmarks
Determining if transducer automaton has two states with intersecting images, without minimizing?
2 answers
8 votes
265 views
2 bookmarks
Cheap online selection with weighted comparisons
1 answers
7 votes
1k views
2 bookmarks
Test set and benchmarks for linear programming
2 answers
6 votes
329 views
3 bookmarks
Infinite process balls in bins problem
1 answers
6 votes
362 views
1 bookmarks
Complexity of finding the largest induced subgraph with all even degrees