# 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

### 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).

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.