2017
Jan
23

# Combinatorics: Elchanan Mossel (MIT) "Lower Bounds on Same-Set Inner Product in Correlated Spaces"

11:00am to 1:00pm

## Location:

Rothberg B220 (CS bldg)

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,