Speaker: Elchanan Mossel (MIT)

Title: Lower Bounds on Same-Set Inner Product in Correlated Spaces

Abstract: Suppose we pick X uniformly from {0,1,2}^n and Y is picked by letting each Y(i) = X(i) or

X(i) + 1 mod 3 with probability 0.5 each independently.

Is it true that for every set S with |S| > c 2^n it holds that the probability that both X and Y are in S is at least g(c) > 0, where g does not depend on the dimension n?

Similar questions were asked before in different contexts. For example,

when X, Y and Z are chosen to be a combinatorial line we can ask if there is a dimension free lower bound on the probability that X, Y and Z are all in S. Here many results are known from additive combinatorics.

Still the answer to the original question in the abstract was not known prior to our work.

In the talk, I will describe the answer to the question above as well as many generalization for sequences of length 2 or more.

Based on a joint work with Jan Hązła and Thomas Holenstein

https://arxiv.org/pdf/1509.06191v1.pdf

Title: Lower Bounds on Same-Set Inner Product in Correlated Spaces

Abstract: Suppose we pick X uniformly from {0,1,2}^n and Y is picked by letting each Y(i) = X(i) or

X(i) + 1 mod 3 with probability 0.5 each independently.

Is it true that for every set S with |S| > c 2^n it holds that the probability that both X and Y are in S is at least g(c) > 0, where g does not depend on the dimension n?

Similar questions were asked before in different contexts. For example,

when X, Y and Z are chosen to be a combinatorial line we can ask if there is a dimension free lower bound on the probability that X, Y and Z are all in S. Here many results are known from additive combinatorics.

Still the answer to the original question in the abstract was not known prior to our work.

In the talk, I will describe the answer to the question above as well as many generalization for sequences of length 2 or more.

Based on a joint work with Jan Hązła and Thomas Holenstein

https://arxiv.org/pdf/1509.06191v1.pdf

## Date:

Mon, 23/01/2017 - 11:00 to 13:00

## Location:

Rothberg B220 (CS bldg)