Lower Bounds for Elimination via Weak Regularity
Result description
We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. [4] for its connection to the famous direct sum question. In this problem, let f be any boolean function. Alice and Bob get k inputs x_1, . . . , x_k and y_1, . . . , y_k respectively. They want to output a k-bit vector v, such that there exists one index i for which v_i is not equal to 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 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.
Keywords
greater-thanregularitydiscrepancyeliminationcommunication complexity
The result's identifiers
Result code in IS VaVaI
Result on the web
http://drops.dagstuhl.de/opus/volltexte/2017/7012/pdf/LIPIcs-STACS-2017-21.pdf
DOI - Digital Object Identifier
Alternative languages
Result language
angličtina
Original language name
Lower Bounds for Elimination via Weak Regularity
Original language description
We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. [4] for its connection to the famous direct sum question. In this problem, let f be any boolean function. Alice and Bob get k inputs x_1, . . . , x_k and y_1, . . . , y_k respectively. They want to output a k-bit vector v, such that there exists one index i for which v_i is not equal to 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 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
R - Projekt Ramcoveho programu EK
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
ISBN
978-3-95977-028-6
ISSN
1868-8969
e-ISSN
neuvedeno
Number of pages
14
Pages from-to
1-14
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl, Germany
Event location
Hannover
Event date
Mar 8, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—
Basic information
Result type
D - Article in proceedings
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Year of implementation
2017