Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ONE-WAY BROADCASTING PROTOCOLS:
Reports tagged with One-way Broadcasting protocols:
TR18-169 | 18th September 2018
Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev

Optimality of Linear Sketching under Modular Updates

We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in $n$ dimensions,
the existence of efficient streaming algorithms which can process $\Omega(n^2)$ updates implies efficient linear sketching algorithms with comparable cost.
This improves upon the previous work ... more >>>




ISSN 1433-8092 | Imprint