Tag Info

New answers tagged

3

Exhaustively checking the first few terms (by examining all n^n cases) and a bit of lookup shows that the answer is https://oeis.org/A036276 / $n^n$. This implies that the answer is $\sim n^{\frac{1}{2}} \frac{\sqrt{\pi}}{2}$. More exactly, the answer is: $$ \frac{n!}{2 n^n} \sum_{k=0}^{n-2}\frac{n^k}{k!} $$ and there is no closed-form answer.


3

If we restrict attention to graph properties, then we can prove slightly improved bounds compared to the general bounds you mention: In a classic paper it was shown that $D(f)$ is bounded by $O(Q(f)^6)$ for total functions, $O(Q(f)^4)$ for monotone total functions, and $O(Q(f)^2)$ for symmetric total functions. First I think the 6th power bound can be ...


4

The answer to both questions is yes. The standard reduction from 3-SAT to 3DM – as used by Garey and Johnson, for example – is not parsimonious, but there is a sequence of parsimonious reductions that goes: 3-SAT → 1-IN-3-SAT → MONOTONE-1-IN-3-SAT → 3DM Moreover, these reductions can be done in a way that preserves planarity. The details can be found in ...


4

[Edit 2014-08-13: Thanks to a comment by Peter Shor, I have changed my estimate of the asymptotic growth rate of this series.] My belief is that $\lim_{n\to\infty} \sum_{i<n} \Pr(E_i)$ grows as $\sqrt{n}$. I do not have a proof but I think I have a convincing argument. Let $B_i = f(i)$ be a random variable that gives the number of balls in bin $i$. Let ...


13

The answer is $\Theta(\sqrt{n})$. First, let's compute $E_{n-1}$. Let's suppose we throw $n$ balls into $n$ bins, and look at the probability that a bin has exactly $k$ balls in it. This probability comes from the Poisson distribution, and as $n$ goes to $\infty$ the probability that there are exactly $k$ balls in a given bin is $\frac{1}{e} \frac{1}{ ...


5

Letting $L$ be the complement of the language of copies $\{ww \mid w \in \{a, b\}^*\}$, you get your statement. First, it is indeed recognized by a NCM — as is the complement of the language of palindromes. The NCM simply ensures that two positions in the input word chosen non deterministically hold different letters, and checks that they are separated by ...


7

There is a general theory here, which was introduced into CS by Robin Milner, which Lamport did not go into. A state machine is generally given as a triple $(Q \in \mathrm{Set}, q \in Q, f \in I \times Q \to \mathcal{P}(O \times Q))$, consisting of a state set $Q$, an initial state $q$, and a transition relation $f$. Now, suppose we have two automata ...


2

Note that in optimization, "convergence rate" usually means asymptotic behavior. That is, the rate only applies to the neighborhood of optimal solutions. In that sense, Luo & Tseng did prove linear convergence rates for some non-strongly convex objective functions in the paper "On the convergence of the coordinate descent method for convex differentiable ...


4

Rather than computing the VC dimension of a particular function class, it's usually more interesting to understand how generic properties of a function class relate to its VC dimension. For example, function spaces with linear dimension $d$ have VC-dim at most $d$. You can also bound the VC-dim of a function class realized by circuits with bounded ...



Top 50 recent answers are included