2 papers
cs.DS2016
Tight Hardness Results for Maximum Weight Rectangles
Arturs Backurs, Nishanth Dikkala, Christos Tzamos
Given weighted points (positive or negative) in dimensions, what is the axis-aligned box which maximizes the total weight of the points it contains? The best known algorith…
cs.DS2015
Nearly-optimal bounds for sparse recovery in generic norms, with applications to -median sketching
Arturs Backurs, Piotr Indyk, Eric Price +2
We initiate the study of trade-offs between sparsity and the number of measurements in sparse recovery schemes for generic norms. Specifically, for a norm , sparsity par…