Wednesday, April 5th, 2017 16:10
Schreiber 309

Random Sampling and the Vector in Subspace Problem
Uri Grupel, Weizmann
Abstract:
Let A be a set on the n dimensional sphere, and let H be a random subspace of dimension n/2.
What can we say about the measure of the intersection? How close is it to the measure of the original set A?
Klartag and Regev gave an optimal answer for this question for large enough sets.
We
will discuss how considering both the intersection with H and with its
orthogonal complement simultaneously may give a better result for
smaller sets.
We prove a partial result under some additional geometric condition.
One motivation to these results is a communication complexity problem called Vector in Subspace Problem (VSP).
In VSP, Alice and Bob attempt to decide either a vector is in a given subspace or in its orthogonal complement.
Using
the concentration of measure results, we can give lower bounds on the
number of bits they need to communicate to each other.