Elimination and Weak Regularity

We will consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. for its connection to the famous direct sum question. In this problem, let $f : \{0, 1\}^{2n} \rightarrow \{0, 1\}$ be any boolean function. Alice and Bob get k inputs $x_1 , \cdots, x_k$ and $y_1 , \cdots, y_k$ respectively, with $x_i , y_i \in \{0, 1\}^n$ . They want to output a $k$-bit vector $v$, such that there exists one index $i$ for which $v_i = f (x_i , y_i )$. We will prove a general result lower bounding the randomized communication complexity of the elimination problem for $f$ using its discrepancy. Consequently, we will obtain strong lower bounds for the functions Inner-Product and Greater-Than. To prove this result, we will use a pseudo-random notion called regularity that was first used by Raz and Wigderson. We will show that functions with small discrepancy are regular. We will also observe that a weaker notion, that we call weak-regularity, already implies hardness of elimination.