Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LINEAR SKETCHING:
Reports tagged with linear sketching:
TR16-174 | 7th November 2016
Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev

#### Linear Sketching over $\mathbb F_2$

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high ... more >>>

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