# Tag Info

Accepted

### "Almost all objects have property P" vs. "It is easy to test whether an object has property P"

They are separate (assuming $P \ne NP$). Consider the following property $P(x)$: $x$ is a $2n$-bit string, where either the first $n$ bits are not all zeros, or the last $n$ bits are a yes-instance ...
Accepted

Accepted

### Why is differential privacy defined over the exponential function?

This answer may be disappointing, but working on a log scale really mostly just makes the formulas nicer. The definition, as written, has the following important properties: Composition: If $A(\cdot)$...
Accepted

### Graph that maximizes minimum hitting time?

It is well known that a barbell graph (two cliques of size $n/3$ connected by a path of length $n/3$) has average hitting time $\Omega(n^3)$, but I believe the same applies to minimum hitting time (...
Accepted

### What are bounded-treewidth circuits good for?

We now understand that for any fixed bound $k \in \mathbb{N}$ on the treewidth, we can convert any Boolean circuit of treewidth less than $k$ to a so-called d-SDNNF circuit, in linear time and with ...
Accepted

### Heterogeneous Hoeffding/McDiarmid

Yes. See for example the stronger concentration for the occupancy problem in the following note: http://sarielhp.org/teach/17/b/lec/10_martin_II.pdf Theorems 10.3.1 and 10.3.2. (This is also covered ...

### Can the "mutual independence" condition in the Lovász local lemma be weakened?

The Lopsided Lovasz Local Lemma relaxes the mutual independence condition to negative dependence. We assume we have events $A_1, \ldots, A_n$, with a lopsidependency graph $G$ defined on $[n]$ s.t. ...

### Exponential Concentration Inequality for Higher-order moments of Gaussian Random Variables

See Theorem 23 in Section 9.3 of Ryan O'Donnell's book Analysis of Boolean functions. Even though the theorem there is stated for $\pm 1$ variables, it holds for Gaussians as well (see Chapter 10 of ...
Accepted

### Which graph parameters are NOT concentrated on random graphs?

Many parameters of the largest connected component are not concentrated for $G(n,p)$ if $p=1/n$ and more generally if $p$ is in the critical window. Examples are the diameter and the size of the ...

### Expected Kolmogorov complexity under Kolmogorov complexity distribution

If $\alpha$ is the answer to the 1st question then $\alpha=\infty$. Namely, for any $c$ there is an $n$ such that all strings $w$ of length at least $n$ have $K (w) \ge c$. In particular the ...
Accepted

### Statistical distance between uniform and biased coin

Denote the random bits by $x_1,\dots, x_n$. By definition, the statistical distance between $U$ and $D$ is at least $\Pr_U\left(\sum x_i \geq t\right) - \Pr_D\left(\sum x_i \geq t\right)$ for every $t$...
Accepted

Accepted

### Isolation Lemma over finite fields

Here is an alternative (and, hopefully, simpler) proof of Neal Young’s argument. To simplify the presentation, I take the set $\def\S{\mathcal S}\S$ of all $2^n-1$ nonempty subsets of $[n]$, and a ...

### An upper bound for chi-square divergence in terms of KL divergence for general alphabets

Your definition of $\chi^2$ divergence is missing a term; namely, $$\chi^2(P\|Q) = \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ} - 1\right)^2 = \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ}\right)^2 - 1$$ (...

### Reverse Chernoff bound

The Generalized Littlewood-Offord Theorem isn't exactly what you want, but it gives what I think of as a "reverse Chernoff" bound by showing that the sum of random variables is unlikely to fall within ...
Accepted

### Squared Hellinger distance between Binomial(n,p) and Binomial(n+1,p)

Write \begin{align} h^2(B(n,p), B(n+1,p))& = 2 \left(1 - \sum_{i=0}^{n+1}\sqrt{{n \choose i}p^i(1-p)^{n-i}{n+1 \choose i} p^i (1-p)^{n+1-i}}\right)\\ &=2\left(1 - \sum_{i=0}^{n+1}\sqrt{\left(...
A somewhat more elementary, and slightly messier proof (or at least it feels so to me). For convenience, write $\varepsilon = \frac{\gamma}{\sqrt{n}}$, with $\gamma\in [0,1)$ by assumption. We ...