Simulation Beats Richness: New Data-Structure Lower Bounds

• Type: Article in International Conference Proceedings Book
• Date: 2018

Authors

Chattopadhyay, A (Author) Other; Koucky, M (Author) Other; Loff, B (Author) FCUP; Mukhopadhyay, S (Author) Other

Conference proceedings International

Title: STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING

Pages: 1013-1020

50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC)

Los Angeles, CA, JUN 25-29, 2018

Indexing

ISI Web of Knowledge - 1 Citation

Scopus - 4 Citations

Other information

Authenticus ID: P-00N-9SR

DOI: 10.1145/3188745.3188874

Abstract (EN): We develop a 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 a novel simulation theorem: Alice gets a p x n matrix x over F-2 and Bob gets a vector y is an element of F-2(n). Alice and Bob need to evaluate f (x center dot y) for a Boolean function f : {0, 1}(p) -> {0, 1}. Our simulation theorems show that a deterministic/randomized communication protocol exists for this problem, with cost C center dot n for Alice and C for Bob, if and only if there exists a deterministic/randomized parity decision tree of cost Theta(C) for evaluating f. As applications of this technique, we obtain the following results: (i) The first strong lower-bounds against randomized data-structure schemes for the Vector-Matrix-Vector product problem over F-2. Moreover, our method yields strong lower bounds even when the data-structure scheme has tiny advantage over random guessing. (ii) The first lower bounds against randomized data-structures schemes for two natural Boolean variants of Orthogonal Vector Counting. (iii) 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.. This seems to be the first known limitation of the Richness Method in the context of proving deterministic lower bounds.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 8