33 citations · 84 across the 22 of their papers we have counts for
4 papers · 1 filter
Improved Frequency Estimation Algorithms with and without Predictions
Anders Aamand, Justin Y. Chen, Huy Lê Nguyen +2
Estimating frequencies of elements appearing in a data stream is a key task in large-scale data analysis. Popular sketching approaches to this problem (e.g., CountMin and CountSket…
Tight Bounds for Volumetric Spanners and Applications
Aditya Bhaskara, Sepideh Mahabadi, Ali Vakilian
Given a set of points of interest, a volumetric spanner is a subset of the points using which all the points can be expressed using "small" coefficients (measured in an appropriate…
Learning the Positions in CountSketch
Yi Li, Honghao Lin, Simin Liu +2
We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem, e.g.,…
Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment
Eden Chlamtáč, Yury Makarychev, Ali Vakilian
We provide new approximation algorithms for the Red-Blue Set Cover and Circuit Minimum Monotone Satisfying Assignment (MMSA) problems. Our algorithm for Red-Blue Set Cover achieves…