ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-165 | 30th October 2016 15:05

Lower Bounds for Elimination via Weak Regularity

RSS-Feed




TR16-165
Authors: Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay
Publication: 30th October 2016 15:15
Downloads: 287
Keywords: 


Abstract:

We 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\}^n \to \{0,1\}$ be any boolean function. Alice and Bob get $k$ inputs $x_1,\ldots,x_k$ and $y_1,\ldots,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 \ne f(x_i,y_i)$. We prove a general result lower bounding the randomized communication complexity of the elimination problem for $f$ using its discrepancy. Consequently, we obtain strong lower bounds for functions Inner-Product and Greater-Than, that work for exponentially larger values of $k$ than the best previous bounds.

To prove our result, we use a pseudo-random notion called regularity that was first used by Raz and Wigderson. We show that functions with small discrepancy are regular. We also observe that a weaker notion, that we call weak-regularity, already implies hardness of elimination. Finally, we give a different proof, borrowing ideas from Viola, to show that Greater-Than is weakly regular.



ISSN 1433-8092 | Imprint