On the optimality of truncation among binary linear sketches

Robinson D. H. Cung, Adway Girish, Emre Telatar

We study statistical inference and function evaluation problems in which the input binary vector is available only through a binary linear sketch, i.e., a fixed number of parity me…