Test your intuition

Sign up for the new posts via the RSS feed.

new job is a good reason to start a (new) blog. The first post is in the spirit of the series by Gil Kalai.

Let $K$ be a convex body in $\mathbb{R}^d$ symmetric around the origin. Let $\mathcal{D}_1$ be a distribution supported on $K$, and let $\mathcal{D}_2$ be a distribution supported outside of $2K$. Can one always find a direction $v$ such that given projections of $\mathrm{poly}(d)$ i.i.d. samples from $\mathcal{D}_i$ on $v$, one can recover $i$ with high probability?

For example, suppose that $K = [-1, 1]^d$ is a cube. Then, each point in the support of $\mathcal{D}_2$ has at least one coordinate whose absolute value is large. It means that there exists a coordinate such that with probability at least $1/d$ over $\mathcal{D}_2$ it is outside of $[-2, 2]$. But then, using this coordinate, one can distinguish $\mathcal{D}_1$ and $\mathcal{D}_2$ using only $O(d)$ samples.

Clement Canonne

So, what is the answer? I really want to know by how much my intuition is off.

Ilya Razenshteyn

The answer is that it’s not always possible: there are examples, when you need 2^{d^{Omega(1)}} queries.

Clement Canonne

It *was* far off then. Are these examples for “pathological” D_1 and D_2, pathological D_1, pathological D_2, or natural D_1, D_2?