Skip to content

10:20-12:00, 37/201. Uri Grupel: "Sampling by Random Intersections".

Mar. 19, 2018

Room 201 building 37

Given a subset of the sphere and a random subspace, what can we say about the measure of their intersection compared to the measure of the subset?

We will discuss this question in two different regimes, for high dimensional subspaces and for low dimensional ones.

The question of intersections with high dimensional subspaces was studied in order to find a lower bound for the communication complexity of the Vector in Subspace Problem.

The second question is related to conductance of hit and run, which is an ingredient in the study of sampling/volume algorithms.

For this question, we will see a sharp contrast between random intersections on the sphere and inside convex bodies.