Personal tools
You are here: Home CG seminar Spring 2017 Random Sampling and the Vector in Subspace Problem
« November 2017 »
November
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
2627282930
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