Chattopadhyay, Arkadev ;
Dvorák, Pavel ;
Koucký, Michal ;
Loff, Bruno ;
Mukhopadhyay, Sagnik
Lower Bounds for Elimination via Weak Regularity
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}^2n > {0,1} be any boolean function. Alice and Bob get k inputs x_1, ..., x_k and y_1, ..., y_k respectively, with x_i,y_i in {0,1}^n. They want to output a kbit vector v, such that there exists one index i for which v_i is not equal 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 the functions InnerProduct and GreaterThan, that work for exponentially larger values of k than the best previous bounds.
To prove our result, we use a pseudorandom 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 weakregularity, already implies hardness of elimination. Finally, we give a different proof, borrowing ideas from Viola, to show that GreaterThan is weakly regular.
BibTeX  Entry
@InProceedings{chattopadhyay_et_al:LIPIcs:2017:7012,
author = {Arkadev Chattopadhyay and Pavel Dvor{\'a}k and Michal Kouck{\'y} and Bruno Loff and Sagnik Mukhopadhyay},
title = {{Lower Bounds for Elimination via Weak Regularity}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {21:121:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770286},
ISSN = {18688969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7012},
URN = {urn:nbn:de:0030drops70128},
doi = {10.4230/LIPIcs.STACS.2017.21},
annote = {Keywords: communication complexity, elimination, discrepancy, regularity, greaterthan}
}
06.03.2017
Keywords: 

communication complexity, elimination, discrepancy, regularity, greaterthan 
Seminar: 

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Issue date: 

2017 
Date of publication: 

06.03.2017 