2.2k citations
- IBM (United States)US73 papers
- Stanford UniversityUS62 papers
- IBM Research - Thomas J. Watson Research CenterUS42 papers
- University of California, BerkeleyUS22 papers
- IBM Research - ZurichCH21 papers
- California Institute of TechnologyUS20 papers
- École Polytechnique Fédérale de LausanneCH15 papers
- Massachusetts Institute of TechnologyUS14 papers
- Max Planck Institute of Microstructure PhysicsDE13 papers
- ETH ZurichCH10 papers
- Princeton UniversityUS10 papers
- SLAC National Accelerator LaboratoryUS10 papers
6 papers · 2 filters
Tight Bounds for Distributed Functional Monitoring
David P. Woodruff, Qin Zhang
We resolve several fundamental questions in the area of distributed functional monitoring, initiated by Cormode, Muthukrishnan, and Yi (SODA, 2008). In this model there are sit…
Beating Randomized Response on Incoherent Matrices
Moritz Hardt, Aaron Roth
Computing accurate low rank approximations of large matrices is a fundamental data mining task. In many applications however the matrix contains sensitive information about individ…
Symmetry and approximability of submodular maximization problems
Jan Vondrak
A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the v…
(1+eps)-approximate Sparse Recovery
Eric Price, David P. Woodruff
The problem central to sparse recovery and compressive sensing is that of stable sparse recovery: we want a distribution of matrices A in R^{m\times n} such that, for any x \in R^n…
Fast approximation of matrix coherence and statistical leverage
Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney +1
The statistical leverage scores of a matrix are the squared row-norms of the matrix containing its (top) left singular vectors and the coherence is the largest leverage score.…
On Variants of the Matroid Secretary Problem
Shayan Oveis Gharan, Jan Vondrák
We present a number of positive and negative results for variants of the matroid secretary problem. Most notably, we design a constant-factor competitive algorithm for the "random…