Neal Young
  • Member for 9 years, 11 months
  • Last seen this week
Reverse Chernoff bound
Accepted answer
29 votes

Here is an explicit proof that a standard Chernoff bound is tight up to constant factors in the exponent for a particular range of the parameters. (In particular, whenever the variables are 0 or 1, ...

View answer
Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers
26 votes

Luca, since a year has passed, you probably have researched your own answer. I'm answering some of your questions here just for the record. I review some Lagrangian-relaxation algorithms for the ...

View answer
Examples of algorithms and proofs that seem correct, but aren't
Accepted answer
20 votes

2D local maximum input: 2-dimensional $n \times n$ array $A$ output: a local maximum -- a pair $(i,j)$ such that $A[i,j]$ has no neighboring cell in the array that contains a strictly larger value. ...

View answer
NP-hard problems with very fast exponential-time algorithms
Accepted answer
16 votes

The desired property holds for Independent Set (and probably other problems) in graphs of suitably bounded tree width. Fix any constant $\epsilon>0$ and consider the Independent Set problem ...

View answer
Sorting using a black box
Accepted answer
16 votes

It's possible to sort with $O(\sqrt n\log n)$ calls to the black box and no comparisons. First, consider the following balanced partitioning problem: given $m$ elements $A[1..m]$ (where $\sqrt n \le ...

View answer
A game of positioning overlapping circles to maximize travel time between them
Accepted answer
15 votes

This answer has two parts, together showing that the correct bound is $\Theta(\log N)$: A lower bound of $\Omega(\log N)$ (times the radius of the first circle). A matching upper bound of $O(\log N)$....

View answer
Does the uncomputability of Kolmogorov complexity follow from Lawvere's Fixed Point Theorem?
14 votes

EDIT: Adding the caveat that Roger's fixed-point theorem may not be a special case of Lawvere's. Here is a proof that may be "close"... It uses Roger's fixed-point theorem instead of Lawvere's ...

View answer
Balls and Bins analysis in the $m \gg n$ regime: gaps
14 votes

For your first question, I think you can show that w.h.p. $X_{\max}-X_{\textrm{sec-max}}$ is $$o\left(\sqrt{\frac{m}{n}\frac{\log^2\log n}{\log n}}\right).$$ Note that this is $o(\sqrt{m/n})$. ...

View answer
Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
Accepted answer
13 votes

You're right that the standard reduction from 3-SAT to 3D-matching (3DM) is not parsimonious. For the record, here's a sketch of a reduction that is parsimonious. It is obtained by composing ...

View answer
Any fundamental papers in TCS which were found to be incorrect/wrong later?
13 votes

A paper in STOC 1994 claimed a poly-time constant-factor approximation algorithm for finding balanced separators and some related problems, but the (incomplete) proofs in that paper are now considered ...

View answer
Approximation algorithm for finding the maximum common subgraph in two DAGs
Accepted answer
12 votes

Isn't there a straightforward approximation-preserving reduction from maximum independent set (MIS) in undirected graphs to your problem? Given undirected graph G=(V,E), form DAG A=(V,E') by ...

View answer
Robustness of splitting a junta
12 votes

The smallest $c$ that the bound holds for is $c = \frac{1}{\sqrt 2 - 1} \approx 2.41$. Lemmas 1 and 2 show that the bound holds for this $c$. Lemma 3 shows that this bound is tight. (In comparison, ...

View answer
Splitting a graph into minimum number of subpaths
11 votes

Your problem (as stated) seems to be NP-hard. Here is a reduction from Partition. Given an instance of Partition (a collection $x_1,\ldots,x_n$ of positive integers), construct a graph with $n+1$ ...

View answer
Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?
Accepted answer
10 votes

EDIT: Added Lemma 2 which covers all cases asked about. Lemma 1. Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, ...

View answer
Number of connected components of a random nearest neighbor graph?
10 votes

EDIT 2: Made explicit the underlying non-asymptotic bounds in the calculation. EDIT: Replaced the calculation for two dimensions by the case of arbitrary constant dimension. Added a table of the ...

View answer
Approximate 1d TSP with linear comparisons?
Accepted answer
10 votes

EDIT (UPDATE): The lower bound in my answer below was proven (by a different proof) in "On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees", by Das et al; ...

View answer
Lower bound on number of oracle calls for solving $n$ instances of the halting problem
10 votes

EDIT: The argument that I had answered with was not wrong, but it was a bit misleading, in that it only showed that the upper bound had to be tight for some $n$ (which is actually trivial, since it ...

View answer
Finding appropriate spanning tree of connected bipartite graph
Accepted answer
10 votes

Isn't this a special case of matroid intersection, which is solvable in polynomial time? Fix your graph $G$ and any integer $d \in \{0,1,\ldots,\max_i a_i\}$. You want to maximize $d$; you can try ...

View answer
How to analyze a randomized recursive algorithm?
Accepted answer
9 votes

Here is a proof that this algorithm runs in $O(n\,m)$ time in expectation and with high probability. First consider the algorithm modified so that $k$ is chosen in $\{2,3,..,\min(c,n)\}$ instead of ...

View answer
Is there a randomized algorithm for set-cover?
8 votes

Here's one randomized $O(\log n)$-approximation algorithm (not well known I'm afraid), for unit-cost set cover. input: collection of sets over $n$ elements, upper bound $U$ on opt output: w/...

View answer
Random sampling data structure with removal
Accepted answer
8 votes

Copying my comment on that from here: There exist published algorithms that support sampling from discrete probability distributions in O(1) time, AND modifying the distribution in O(1) time per ...

View answer
Examples of Computer-Found Optimal Strategies in Games
8 votes

See Wolfe and Berlekamp -- Mathematical Go. Using Conway's theory of games, they show how to analyze certain kinds of Go endgames. Their solutions turn out to be measurably better than the solutions ...

View answer
Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$
Accepted answer
8 votes

Time $O(d^3\log d)$ lemma: Fix any $x\in[0,1]^d$. Then there is a set $S$ containing $d+1$ corners of $\{0,1\}^d$ that are closest to $x$ and such that $S$ is connected (meaning that the subgraph of ...

View answer
Any graph $G$ can be seen as the sum of complete $k_i$-partite graphs?
Accepted answer
8 votes

I think the answer to your first question is "no". In particular, if you take a random bipartite graph $G=([n],[n],E)$ where $Pr[(i,j)\in E] = 1/2$ for each pair $(i,j)$, the answer is no with ...

View answer
What is the complexity of this covering problem?
8 votes

Although this does not resolve the question you raise, some of the previous comments consider approximation algorithms. FWIW, I think a PTAS (poly-time approximation scheme) is possible using dynamic ...

View answer
Find negative cycle with vertex constraints
8 votes

If you don't require the cycle to be simple, then break the (directed) graph into its strongly connected components, and for each component containing one of the given vertices $V_i$, check whether ...

View answer
Does Horn SAT (Horn formula in CNF) have an integral polytope?
Accepted answer
7 votes

EDIT: Strengthened Theorem 2. The answer to the problem as posed is no, unless P=NP: Theorem 1. Unless P=NP, there is no LP polytope for Horn-SAT that has only integer extreme points and is ...

View answer
Additive versus multiplicative accuracy
Accepted answer
7 votes

Why is it sometimes easier to achieve $\epsilon$-additive accuracy than $\epsilon$-multiplicative? Consider a problem where the objective value OPT is guaranteed to lie in a constant non-negative ...

View answer
Can we decide whether a permanent has a unique term?
Accepted answer
7 votes

EDIT - 2/11/20 - barring mistakes, this should answer the posted question. Summary. Define a new complexity class, UW-NP, containing languages definable as follows: given any poly-time non-...

View answer
Coupon collector - the effect of randomization
Accepted answer
7 votes

$E[m]$ equals $n(H_n-1)$. Here's a more complete proof sketch, following the argument suggested in my comment. We start by showing that each permutation of the first $k-1$ elements is equally ...

View answer