13. Finding Subsets of Vectors with Large Average Correlation
-
Problem 13.1.
[Alex Andoni] For $\varepsilon,\delta>0$ and unit vectors $v_1,v_2,\dots v_n \in \ell_2$, consider the following two properties: (a) $\langle v_i,v_j \rangle \leq 2\varepsilon$ whenever $i \neq j$ and (b) there exists $A \subseteq \{1,2,\dots n\}$ such that $|A| \geq n^{1-\delta}$ and $\langle v_i,v_j \rangle \geq \varepsilon$ for all $i,j \in A$. What is the largest $\delta$, in terms of $\varepsilon$, such that for any unit vectors $v_1,v_2 \dots v_n \in \ell_2$ satisfying (a) and (b), there exists $I \subseteq \{1,2,\dots n\}$ with $|I| \geq n^{1-O(\delta)}$ and $\frac{1}{|I|^2}\sum_{i,j\in I} \langle v_i,v_j \rangle = \Omega(\varepsilon)$?
Cite this as: AimPL: Metric embeddings, available at http://aimpl.org/metricembeddings.