Simulation beats richness: new data-structure lower bounds
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Simulation beats richness: new data-structure lower bounds
Original language description
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'94) and Miltersen, Nisan, Safra and Wigderson (STOC'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 '95). This seems to be the first known limitation of the Richness Method in the context of proving deterministic lower bounds.
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
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2018
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
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
Number of pages
8
Pages from-to
1013-1020
Publisher name
ACM New York, NY, USA
Place of publication
New York, NY, USA
Event location
Los Angeles, CA, USA
Event date
Jun 25, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—