# tcs math – some mathematics of theoretical computer science

## June 26, 2013

### Separated sets in unions of frames

Filed under: Math, Open question — Tags: , , — James Lee @ 11:46 pm

In celebration of the recent resolution of the Kadison-Singer problem by Marcus, Spielman, and Srivastava, here is a question on isotropic point sets on which Kadison-Singer does not (seem to) shed any light. A positive resolution would likely have strong implications for the Sparsest Cut problem and SDP hierarchies. The question arose in discussions with Shayan Oveis Gharan, Prasad Raghavendra, and David Steurer.

Open Question: Do there exist constants $\varepsilon, \delta > 0$ such that for any $k \in \mathbb N$, the following holds? Let $\mathcal B_1, \mathcal B_2, \ldots, \mathcal B_k \subseteq \mathbb R^k$ be a collection of $k$ orthonormal bases and define $W = \mathcal B_1 \cup \mathcal B_2 \cup \cdots \cup \mathcal B_k$. Then there are subsets $A,B \subseteq W$ with $|A|,|B| \geq \varepsilon |W|$ and $\min_{x \in A, y \in B} \|x-y\|_2 \geq \delta$.

[Some additional notes: One piece of intuition for why the question should have a positive resolution is that these $k$ orthonormal bases which together comprise at most $k^2$ vectors cannot possibly "fill" $k$-dimensional space in a way that achieves $k$-dimensional isoperimetry. One would seem to need $\exp(O(k))$ points for this.

One can state an equivalent question in terms of vertex expansion. Say that a graph $G=(V,E)$ on $k^2$ vertices is a vertex expander if $|N(S)| \geq 1.1 |S|$ for all subsets $S \subseteq V$ with $|S| \leq |V|/2$. Here, $N(S)$ denotes all the nodes that are in $S$ or are adjacent to $S$. Then one can ask whether there exists a 1-1 mapping from $V$ to $\mathcal B_1 \cup \cdots \cup \mathcal B_k$ for some orthonormal bases $\{\mathcal B_i\}$ such that the endpoints of every edge are mapped at most $o(1)$ apart (as $k \to \infty$).]

1. What would be the implication for sparsest cut?

Comment by minilek — June 27, 2013 @ 5:22 pm

2. Strictly speaking, there is no direct implication because this question is the “hard part” of a more general question. The more general question is to find such separated sets given any set of $n \leq k^{O(1)}$ unit vectors in isotropic position.

The implication is as follows: For every $\delta > 0$, there is a number $C(\delta)$ such that Sparsest Cut admits a $C(\delta)$-approximation in time $2^{n^{\delta}}$, i.e. sub-exponential time constant factor approximations to (uniform) Sparsest Cut.

Comment by James L. — June 27, 2013 @ 5:26 pm

3. What is your precise definition of isotropic position? Is it that the covariance matrix (the sum of uu^T over vectors u in the set) is a multiple of the identity or is it exactly the identity? Seems like it’s the former, but just want to make sure.

Comment by NG — June 28, 2013 @ 8:25 pm

4. More specifically, the general condition is as follows: Given $n$ unit vectors $v_1, v_2, \ldots, v_n \in \mathbb R^k$, we assume that $\frac{1}{n} \sum_{i=1}^n v_i v_i^T = \frac{1}{k} I$. Of course, a special case is when the vectors $\{v_i\}$ can be partitioned into orthonormal bases.

Comment by James L. — June 28, 2013 @ 10:25 pm

5. Is it important that the bases are over the reals? I think I can see a construction of such sets over complex vector spaces.

Comment by sflammia — July 5, 2013 @ 1:06 am

6. A general construction of such A,B over $\mathbb C^k$ would be equally remarkable (and useful).

Comment by James Lee — July 5, 2013 @ 11:59 am

7. Wow, awesome blog layout! How long have you been blogging
for? you made blogging look easy. The overall look of your web site is wonderful, as well as the
content!

Comment by reading glasses with built in lights — December 6, 2013 @ 4:33 am