Thomas Vidick

Given two sets $A,B\subseteq\R^n$, a measure of their dependence, or correlation, is given by the expected squared inner product between random $x\in A $ and $y\in B$. We prove an inequality showing that no two sets of large enough Gaussian measure (at least $e^{-\delta n}$ for some constant $\delta >0$) ... more >>>

Anup Rao, Amir Yehudayoff

We prove a sharp lower bound on the distributional communication complexity of the exact gap-hamming problem.

more >>>