Neal Young
• Member for 9 years, 11 months
• Last seen this week

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, ...

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 ...

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. ...

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 ...
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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 ...