30 problems

Let $\mathcal{R}$ be the family of random variables of the form $X=\sum_{k=1}^n a_k\varepsilon_k$, where $n\geq 1$, $a_k\in\mathbb{R}$, $\sum_{k=1}^n a_k^2=1$, and the…

Let $(\boldsymbol{\mathrm{P}}\!_n)_{n\geq 1}$ be a sequence of measures on finite product spaces, and let $\Gamma_n(\boldsymbol{\mathrm{P}}\!_n)$ and…

Let $K$ be the unit ball of a norm on $\mathbb R^n$, let $S^{n-1}$ be the Euclidean unit sphere, and let $\sigma$ denote its rotation-invariant probability measure. Write … The sec…

Let $\mu$ be a distribution and let $\mathcal{F}[\mu,\psi]$ denote the relevant concentration objective for a coordinate $\psi$. Given $n$ samples, let $\hat{\psi}_n$ be a data-dri…

Let $\mathcal{P}$ be a distribution family on $(0,\infty)$ whose members have power-law tails satisfying $P(X>x)\sim x^{-\alpha}$ for some $\alpha>0$. Let the logarithmic coordinat…

Erbar–Fathi conjecture. The concentration assumption implies

Concentration conjecture. The same sub-Gaussian concentration phenomenon should hold when the sum $$ is replaced by a more general Lipschitz function of the variables.

Zigzag Conjecture. Set $p=\frac12$. There is a sequence of intervals of length $n^{\lambda+o(1)}$ containing $\chi(G_{n,1/2})$ with high probability. However, for every fixed…

Consider the quantum approximate optimization method applied to sufficiently large instances, together with distant and unrelated shadow defects that can affect the efficacy of low…

Consider low-depth quantum approximate optimization algorithms (QAOA) applied to random problem instances, and the phenomenon described in the surrounding text, in which distant en…

Superiorization strict-improvement conjecture. The considerations based on concentration of measure should imply a conclusion stronger than

Bobkov–Houdré–Tetali conjecture. There exists a vertex $x_0\in V(C_n)$ such that, for every $v\in V(C_n)$,

Tree characterization conjecture. There exists a vertex $r$ such that, for every vertex $u\in V(T)$,

Isoperimetric extremizer conjecture. For $n$ sufficiently large and $d,r$ in appropriate ranges,

Let $\mu$ be a centered log-concave probability measure on $\mathbb R^n$, meaning that … for some convex function $v:\mathbb R^n\to(-\infty,\infty]$. Let $\mathbb E_\mu$ and…

Let $(G_n)$ be a sequence of vertex-transitive graphs with increasing sizes. Let $\mathrm{SC}(G_n)$ be the social connectivity time, and let $\tau_i(G_n)$, $i=1,2$, be the two auxi…

Let $A\subseteq S^{n-1}$ be a measurable subset with $\sigma_{n-1}(A)\geq e^{-c\sqrt{n}}$. For a subspace $H\subseteq\mathbb{R}^n$ of dimension $\lfloor n/2\rfloor$, let…

Non-Lipschitz moment conjecture. There is a constant $C_D$ such that

Let $H$ denote the Hurst parameter of a Gaussian process. The paper's method gives exponential upper bounds for small deviations when $H>\frac12$, although these bounds are not kno…

Variance conjecture. Every log-concave isotropic random vector $X$ satisfies

Variance conjecture—bis. There exists a constant $C$ such that for every isotropic log-concave random vector $X$,

Variance conjecture. There exists a constant $C$ such that for every isotropic log-concave random vector $X$,

Thin shell conjecture. There exists $c>0$ such that for any log-concave isotropic probability on $\mathbb{R}^n$ and any $t>0$,

The standard Gaussian measure on $\mathbb{R}^n$ satisfies the S-inequality: for every convex symmetric set $K$ and the strip $P=\{x\in\mathbb{R}^n:|x_1|\leq p\}$ chosen so that…

Let $X$ be a centered log-concave random vector in $\mathbb R^n$, let $\lambda_X^2$ denote the largest eigenvalue of its covariance matrix, and let $|X|$ be its Euclidean norm. The…