Linear Sketching over ${\mathbb{F}}_2$

Sampath Kannan, Elchanan Mossel, Grigory Yaroslavtsev

We initiate a systematic study of linear sketching over ${\mathbb{F}}_2$. For a given Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ a randomized ${\mathbb{F}}_2$-sketch is a distribu…