Simulation beats richness: new data-structure lower bounds

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10387323" target="_blank" >RIV/00216208:11320/18:10387323 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1145/3188745.3188874" target="_blank" >https://doi.org/10.1145/3188745.3188874</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3188745.3188874" target="_blank" >10.1145/3188745.3188874</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Simulation beats richness: new data-structure lower bounds

Popis výsledku v původním jazyce

We develop a new technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC&apos;94) and Miltersen, Nisan, Safra and Wigderson (STOC&apos;95). At the core of our technique is the first simulation theorem in the asymmetric setting, where Alice gets a p x n matrix x over F2 and Bob gets a vector y ELEMENT OF F2n. Alice and Bob need to evaluate f(x. y) for a Boolean function f: {0,1}p RIGHTWARDS ARROW {0,1}. Our simulation theorems show that a deterministic/randomized communication protocol exists for this problem, with cost C. n for Alice and C for Bob, if and only if there exists a deterministic/randomized *parity decision tree* of cost Θ(C) for evaluating f. As applications of this technique, we obtain the following results: 1. The first strong lower-bounds against randomized data-structure schemes for the Vector-Matrix-Vector product problem over F2. Moreover, our method yields strong lower bounds even when the data-structure scheme has tiny advantage over random guessing. 2. The first lower bounds against randomized data-structures schemes for two natural Boolean variants of Orthogonal Vector Counting. 3. We construct an asymmetric communication problem and obtain a deterministic lower-bound for it which is provably better than any lower-bound that may be obtained by the classical Richness Method of Miltersen et al. (STOC &apos;95). This seems to be the first known limitation of the Richness Method in the context of proving deterministic lower bounds.

Název v anglickém jazyce

Simulation beats richness: new data-structure lower bounds

Popis výsledku anglicky

We develop a new technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC&apos;94) and Miltersen, Nisan, Safra and Wigderson (STOC&apos;95). At the core of our technique is the first simulation theorem in the asymmetric setting, where Alice gets a p x n matrix x over F2 and Bob gets a vector y ELEMENT OF F2n. Alice and Bob need to evaluate f(x. y) for a Boolean function f: {0,1}p RIGHTWARDS ARROW {0,1}. Our simulation theorems show that a deterministic/randomized communication protocol exists for this problem, with cost C. n for Alice and C for Bob, if and only if there exists a deterministic/randomized *parity decision tree* of cost Θ(C) for evaluating f. As applications of this technique, we obtain the following results: 1. The first strong lower-bounds against randomized data-structure schemes for the Vector-Matrix-Vector product problem over F2. Moreover, our method yields strong lower bounds even when the data-structure scheme has tiny advantage over random guessing. 2. The first lower bounds against randomized data-structures schemes for two natural Boolean variants of Orthogonal Vector Counting. 3. We construct an asymmetric communication problem and obtain a deterministic lower-bound for it which is provably better than any lower-bound that may be obtained by the classical Richness Method of Miltersen et al. (STOC &apos;95). This seems to be the first known limitation of the Richness Method in the context of proving deterministic lower bounds.

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

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

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

Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018

ISBN

978-1-4503-5559-9

ISSN

—

e-ISSN

neuvedeno

Počet stran výsledku

8

Strana od-do

1013-1020

Název nakladatele

ACM New York, NY, USA

Místo vydání

New York, NY, USA

Místo konání akce

Los Angeles, CA, USA

Datum konání akce

25. 6. 2018

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

WRD - Celosvětová akce

Kód UT WoS článku

—