Neal Young's user avatar
Neal Young's user avatar
Neal Young's user avatar
Neal Young
  • Member for 10 years, 8 months
  • Last seen this week
31 votes
Accepted

Reverse Chernoff bound

26 votes

Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

20 votes
Accepted

Examples of algorithms and proofs that seem correct, but aren't

16 votes
Accepted

NP-hard problems with very fast exponential-time algorithms

16 votes
Accepted

Sorting using a black box

15 votes
Accepted

A game of positioning overlapping circles to maximize travel time between them

14 votes

Does the uncomputability of Kolmogorov complexity follow from Lawvere's Fixed Point Theorem?

14 votes

Balls and Bins analysis in the $m \gg n$ regime: gaps

14 votes
Accepted

Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?

13 votes

Any fundamental papers in TCS which were found to be incorrect/wrong later?

12 votes

Robustness of splitting a junta

12 votes
Accepted

Approximation algorithm for finding the maximum common subgraph in two DAGs

11 votes

Splitting a graph into minimum number of subpaths

10 votes
Accepted

Approximate 1d TSP with linear comparisons?

10 votes
Accepted

Finding appropriate spanning tree of connected bipartite graph

10 votes

Lower bound on number of oracle calls for solving $n$ instances of the halting problem

10 votes
Accepted

Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

10 votes

Number of connected components of a random nearest neighbor graph?

9 votes

Quadratic lower bound

9 votes
Accepted

How to analyze a randomized recursive algorithm?

8 votes

Is there a randomized algorithm for set-cover?

8 votes

What is the complexity of this covering problem?

8 votes

Find negative cycle with vertex constraints

8 votes
Accepted

Any graph $G$ can be seen as the sum of complete $k_i$-partite graphs?

8 votes
Accepted

Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$

8 votes

Examples of Computer-Found Optimal Strategies in Games

8 votes
Accepted

Random sampling data structure with removal

7 votes
Accepted

Coupon collector - the effect of randomization

7 votes
Accepted

Is there a simplex-like algorithm that can be used with a separation oracle?

7 votes
Accepted

Can we decide whether a permanent has a unique term?

1
2 3 4 5