3 citations · 15 across the 20 of their papers we have counts for
4 papers · 1 filter
Derandomization of Cell Sampling
Alexander Golovnev, Tom Gur, Igor Shinkar
Since 1989, the best known lower bound on static data structures was Siegel's classical cell sampling lower bound. Siegel showed an explicit problem with inputs and possibl…
Linear Space Streaming Lower Bounds for Approximating CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +2
We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on variables taking values in $\{0…
Sketching approximability of all finite CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +1
A constraint satisfaction problem (CSP), , is specified by a finite set of constraints for positive int…
Approximability of all Boolean CSPs with linear sketches
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +1
In this work we consider the approximability of in the context of sketching algorithms and completely characterize the approximability of all Boolean CSPs. Sp…