User Neal Young

31 votes

Accepted

Reverse Chernoff bound

answered Nov 26, 2012 at 3:56

26 votes

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

answered Nov 19, 2012 at 22:18

20 votes

Accepted

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

answered Mar 31, 2018 at 1:57

16 votes

Accepted

NP-hard problems with very fast exponential-time algorithms

answered Dec 30, 2019 at 16:01

16 votes

Accepted

Sorting using a black box

answered Mar 17, 2013 at 17:49

15 votes

Accepted

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

answered Mar 14, 2013 at 8:55

14 votes

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

answered Mar 24, 2017 at 16:39

14 votes

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

answered Nov 29, 2012 at 23:16

14 votes

Accepted

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

answered Aug 31, 2020 at 18:01

14 votes

Accepted

Complexity of NFA cofiniteness

answered Mar 22 at 21:42

13 votes

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

answered May 31, 2020 at 0:48

13 votes

Accepted

Find odd-ranked numbers from a list

answered Mar 27, 2023 at 18:01

12 votes

Accepted

Expected number of random comparisons needed to sort a list

answered Oct 3, 2022 at 18:22

12 votes

Robustness of splitting a junta

answered Nov 18, 2012 at 0:31

12 votes

Accepted

Approximation algorithm for finding the maximum common subgraph in two DAGs

answered May 20, 2013 at 15:21

11 votes

Splitting a graph into minimum number of subpaths

answered Nov 22, 2012 at 2:12

11 votes

Accepted

Additive versus multiplicative accuracy

answered May 23, 2020 at 16:15

11 votes

Number of connected components of a random nearest neighbor graph?

answered Jun 13, 2020 at 8:03

10 votes

Accepted

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

answered Jun 10, 2020 at 22:31

10 votes

Accepted

Approximate 1d TSP with linear comparisons?

answered Nov 22, 2012 at 19:12

10 votes

Accepted

Finding appropriate spanning tree of connected bipartite graph

answered Mar 18, 2013 at 0:08

10 votes

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

answered Mar 19, 2013 at 19:17

9 votes

Accepted

How to analyze a randomized recursive algorithm?

answered Nov 2, 2012 at 18:55

9 votes

Is there a randomized algorithm for set-cover?

answered Nov 3, 2012 at 2:59

9 votes

Quadratic lower bound

answered Jun 29, 2022 at 1:54

8 votes

Accepted

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

answered Jan 25, 2022 at 14:41

8 votes

What is the complexity of this covering problem?

answered Jun 30, 2012 at 1:07

8 votes

Find negative cycle with vertex constraints

answered Jul 2, 2012 at 5:25

8 votes

Accepted

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

answered Nov 22, 2012 at 21:32

8 votes

Accepted

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

answered Dec 24, 2012 at 16:39

Stack Exchange Network

171 Answers

Reverse Chernoff bound

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

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

NP-hard problems with very fast exponential-time algorithms

Sorting using a black box

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

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

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

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

Complexity of NFA cofiniteness

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

Find odd-ranked numbers from a list

Expected number of random comparisons needed to sort a list

Robustness of splitting a junta

Approximation algorithm for finding the maximum common subgraph in two DAGs

Splitting a graph into minimum number of subpaths

Additive versus multiplicative accuracy

Number of connected components of a random nearest neighbor graph?

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

Approximate 1d TSP with linear comparisons?

Finding appropriate spanning tree of connected bipartite graph

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

How to analyze a randomized recursive algorithm?

Is there a randomized algorithm for set-cover?

Quadratic lower bound

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

What is the complexity of this covering problem?

Find negative cycle with vertex constraints

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

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