Skip to content

Open Problems in Linear Analysis and Probability

The problems here were either submitted specifically for the purpose of inclusion in this page, or were taken from talks given during the
Concentration Week on Metric Geometry and Geometric Embeddings of Discrete Metric Spaces.

Click here to view the PDF version of the file.

Click here to view open problems list on embeddings of finite metric spaces compiled by Jiri Matousek

Problem #1 (Submitted by Guoliang Yu)
Construct a discrete metric space $\Gamma$ with bounded geometry such that $\Gamma$ is coarsely embedable into $l_p$ but not $l_q$ where $p>q\geq 2$.
Problem #2 (Submitted by Guoliang Yu)
Find intrinsic geometric condiion of $\Gamma$ guaranteeing coarse embedability into $l_p$.
Problem #3 (Submitted by Yuval Peres)
What is the minimal possible distortion for an embedding of a $n-$vertex graph of girth $g = c\log n$ in a Euclidean space.
Problem #4 (Submitted by Yuval Peres)
Do planar graphs (with graph distance) have a Markov type 2.
Problem #5 (Submitted by Moses Charikar)
How well do $l_2^2$ (negative type) metrics embed into $l_1$?
Problem #6 (Submitted by Sanjeev Arora)
What is the worst possible value of $C_1(X)$ when the induced metric on every subset of $X$ of size $k$ is $l_1$ (say $k = O(\log n)$)?
Problem #7 (Submitted by Bruce Kleiner)
Characterize metric spaces which bi-Lipschitz embed into $L^2$.
Problem #8 (Submitted by Leonid Kovalev)
Embed doubling metric space into $l_2$ via $f$ ($f : X\to l_2$) such that:
  • $f(X)$ is doubling
  • $d(a,b)\leq \|f(a) - f(b)\|\leq w_f(d(a,b))$ and $w_f$ is as small as possible.
Problem #9 (Submitted by Piotr Nowak)
Do expanders (with constant degree) embed coarsely into any uniformly convex Banach space?
Problem #10 (Submitted by James Lee)
Does every $n$-point doubling metric admits $(1,\infty)$ type embedding with distortion $O(\sqrt{\log n})$?
Problem #11 (Submitted by James Lee)
Let $X\subseteq L_1, |X| = n$. \\
Is there $\displaystyle f : X\to l_1^{O(\log n)}, \|f\|_{Lip} = 1$ such that
\sum_{x,y}\|f(x) - f(y)\|_1\geq \frac{\sum_{x,y}\|x - y\|_1}{C}
for some $C$?
Problem #12 (Submitted by Avner Magen)
Is there a dimension reduction for $l_2^2$ such that if you start with $n$-points with no obtuse angle, after the reduction there is no obtuse angle as well?
Problem #13 (Submitted by James Lee)
Let $(X,d)$ be a metric space such that $C_2(X,\sqrt{d}) \leq O(1)$. Does there exist negative type metric $(Y,d_y)$ so that $(X,d)$ and $(Y,d_y)$ are bi-Lipschitz equivalent?
Problem #14 (Submitted by Assaf Naor)
Let $X\subseteq L_1, |X| = n$. Is it true that
X \stackrel{O(1)} {\hookrightarrow} l_1^{O(\log n)}\oplus l_{\infty}^{O(\log n)}
Problem #15 (Submitted by William Johnson)
  • Is there a composition formula for Lipschitz $p$-summing operators?
  • Are there Lipschitz $p$-summing versions of consequences of Grothendieck's theorem?
Problem #16 (Submitted by James Lee)
Let $X$ be an infinite dimensional metric space. Let $\displaystyle D_n(X,L_2) = \sup_{A\subseteq X, |A| = n} C_2(A)$. If $D_n(X,L_2) = \Omega (\log n)$, then is there a constant degree expander family $\{G_i\}$, such that $G_i$ embeds in $X$ with constant distortion?
Problem #17 (Submitted by Assaf Naor)
Let $a_n = \sup \{ C_2(R^n/\Lambda) | \Lambda$ is a lattice in $R^n\}$. It is known that $n^{4n} \geq a_n \geq c\sqrt{n}$. What is the actual rate of $a_n$?