Personal tools
You are here: Home CG seminar Spring 2017 Random Sampling and the Vector in Subspace Problem
« July 2017 »
Log in

Forgot your password?

Random Sampling and the Vector in Subspace Problem

Wednesday, April 5th, 2017 16:10

Schreiber 309


Random Sampling and the Vector in Subspace Problem

Uri Grupel, Weizmann


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.
Document Actions