Lower Bounds for Elimination via Weak Regularity

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10368568" target="_blank" >RIV/00216208:11320/17:10368568 - isvavai.cz</a>

Výsledek na webu

<a href="http://drops.dagstuhl.de/opus/volltexte/2017/7012/pdf/LIPIcs-STACS-2017-21.pdf" target="_blank" >http://drops.dagstuhl.de/opus/volltexte/2017/7012/pdf/LIPIcs-STACS-2017-21.pdf</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2017.21" target="_blank" >10.4230/LIPIcs.STACS.2017.21</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Lower Bounds for Elimination via Weak Regularity

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Lower Bounds for Elimination via Weak Regularity

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

R - Projekt Ramcoveho programu EK

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

ISBN

978-3-95977-028-6

ISSN

1868-8969

e-ISSN

neuvedeno

Počet stran výsledku

14

Strana od-do

1-14

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl, Germany

Místo konání akce

Hannover

Datum konání akce

8. 3. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—