Personal tools
You are here: Home CG seminar Spring 2017 Random Sampling and the Vector in Subspace Problem
« September 2017 »
September
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
Log in


Forgot your password?
 

Random Sampling and the Vector in Subspace Problem

Wednesday, April 5th, 2017 16:10

Schreiber 309

underline

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