Skip to main content
25 votes
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 ...
D.W.'s user avatar
  • 12.3k
15 votes
Accepted

What is the proof of this nonstandard version of Azuma's inequality?

I can't find a reference, so I'll just sketch the proof here. Theorem. Let $X_1, \cdots, X_n$ be real random variables. Let $a_1, \cdots, a_n, b_1, \cdots, b_n$ be constants. Suppose that, for all $i ...
Thomas's user avatar
  • 2,803
11 votes
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)$...
Sasho Nikolov's user avatar
10 votes
Accepted

What is the connection between moments of Gaussians and perfect matchings of graphs?

This fact is a corollary of a more general theorem. Let $\gamma_1,\dots, \gamma_{2n}$ be (jointly) Gaussian random variables; we don't assume that they are independent or identically distributed. Let $...
Yury's user avatar
  • 3,909
10 votes
Accepted

Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

For notational convenience define r.v.s $T_S = \min\{i : |S_i| = 1\}$ (recalling $S_i = S \cap H_1 \cap \cdots \cap H_i$), and $T_H = \min\big\{i : H_1 \cap H_2 \cap \cdots \cap H_i = \{0^n\}\big\}$. ...
Neal Young's user avatar
  • 10.8k
9 votes
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 ...
a3nm's user avatar
  • 9,677
9 votes
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 ...
Sariel Har-Peled's user avatar
8 votes

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. ...
Sasho Nikolov's user avatar
7 votes
Accepted

Reference for the number of samples needed to distinguish two probability distributions

So here, you only have two options: either your samples come from $p$, or from $q$ (and you know explicitly both). By definition of the statistical/total variation distance, we have $$ d_{TV}(p,q) = \...
Clement C.'s user avatar
  • 4,481
7 votes
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 ...
Yuval Peres's user avatar
7 votes

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 ...
Bjørn Kjos-Hanssen's user avatar
7 votes
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$...
Yury's user avatar
  • 3,909
6 votes

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

The formulation on p.70 of the 4th edition of The Probabilistic Method by Alon and Spencer is along the lines you state.
kodlu's user avatar
  • 2,070
6 votes

Which graph parameters are NOT concentrated on random graphs?

Failure to concentrate happens for some counting ($\#\mathsf{P}$) properties, and maybe for many of them. A simple example is the number of spanning subgraphs ($2^m$). The number of edges of a random ...
David Eppstein's user avatar
6 votes
Accepted

Random Deterministic Automata

The question is a bit ill-posed, since you did not specify that equivalent automata should be counted as a single object. Without that restriction (or the reachability one), the set of all $n$-state ...
Aryeh's user avatar
  • 10.6k
6 votes
Accepted

Statistical Distance Growth Given K Independent Copies

See the "inclusion-exclusion" Lemma 2.2 here https://www.cs.bgu.ac.il/~karyeh/mark-conc2.pdf . For distributions $p,q,p',q'$, we have $$ ||p\otimes q-p'\otimes q'|| \le ||p-p'|| + ||q-q'|| - ||p-p'|| ...
Aryeh's user avatar
  • 10.6k
6 votes
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 ...
Emil Jeřábek's user avatar
5 votes

What is the connection between moments of Gaussians and perfect matchings of graphs?

Here is a different proof, adapted from the monograph The semicircle law, free random variables and entropy. Let $X_i$ be an infinite sequence of i.i.d. variables with distribution $\Pr[X_i = 1] = \Pr[...
Yuval Filmus's user avatar
  • 14.5k
5 votes

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

@odea, one can see that $\chi^2(P||Q) \leq c D(P||Q)$ cannot hold in general by taking a two point space with $P = \{ 1 , 0\}$ and $Q = \{ q, 1-q \}$. Then $\chi^2(P ; Q) = \frac 1 q -1$ while $D(P||Q)...
James Melbourne's user avatar
5 votes

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 $$ (...
Clement C.'s user avatar
  • 4,481
5 votes

Statistical distance between uniform and biased coin

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 ...
Clement C.'s user avatar
  • 4,481
5 votes

A coupon collector type problem with changing probabilities

Lemma. In the unbounded case, the expected number of flips is at most $\sqrt t + 3/2$. Proof. Let r.v. $F$ be the number of flips until a head. Then the expected number of flips is \begin{align} E[F]...
Neal Young's user avatar
  • 10.8k
5 votes
Accepted

If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'

There are 4 possibilities, name them e1-e4: e1 neither match e2 a only matches e3 b only matches e4 both match Now I restate what you want to prove: Suppose: ...
usul's user avatar
  • 7,615
5 votes
Accepted

Big-O bounds on the k-th largest element of iid Gaussians

This is not a complete answer by any means, but just a quick estimate on $\mathbb{E}[\sum_{i=1}^k X_{[i]}]$ that is slightly better than the trivial bound of $O(k\sqrt{\log n})$. If this is your goal, ...
Jason Gaitonde's user avatar
5 votes
Accepted

Relationship between Random Graph Theory and TCS

There are interesting open algorithmic problems in random graphs, which might even lead to nontrivial results about complexity classes. For the sake of an example, consider the simplest random graph ...
Andras Farago's user avatar
5 votes

Isolation Lemma over finite fields

Here is a counter-example showing that at least when $\log m \ll n$ isolation is not possible: with high probability, every weight has exponentially many sets summing to it, so no particular set is &...
Neal Young's user avatar
  • 10.8k
5 votes

Evaluating asymptotic probabilities of First Order Logic Formulas?

By slightly modifying Grandjean's algorithm (reference in Emil's answer), one can show that for any fixed $k\geq 1$ and for a fixed finite (relational) language $L$, the problem of determining the ...
Reijo Jaakkola's user avatar
5 votes
Accepted

Number of random bits necessary to approximate an arbitrary distribution

There is no $H(X)+\log(1/\epsilon)$ bound. I think your $H(X)/\varepsilon$ bound is tight. Example 1. Suppose $X$ is uniformly distributed on $\{1,2,\dots,2^n\}$. Then the optimal encoding has ...
D.W.'s user avatar
  • 12.3k
4 votes

Minimum Spanning tree on a complete "random" graph

Let's consider a general model in which $L_n(\mu)$ is the (random) length of an MST on $K_n$, where the weight of each edge is sampled independently from a probability distribution $\mu$. When $\mu$ ...
Sasho Nikolov's user avatar
4 votes

Approaches for Theoretical Analysis of Estimates of Probability Distributions

Disclaimer: I am biased, in that I will suggest a survey which I have written. What you seem to be looking for can be captured under the field of distribution testing, a subfield of Property Testing ...
Clement C.'s user avatar
  • 4,481

Only top scored, non community-wiki answers of a minimum length are eligible