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
13 papers · 1 filter
Recovery of a Sparse Integer Solution to an Underdetermined System of Linear Equations
T. S. Jayram, Soumitra Pal, Vijay Arya
We consider a system of m linear equations in n variables Ax=b where A is a given m x n matrix and b is a given m-vector known to be equal to Ax' for some unknown solution x' that…
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…
Limitations of randomized mechanisms for combinatorial auctions
Shaddin Dughmi, Jan Vondrak
Recently, a randomized mechanism has been discovered [Dughmi, Roughgarden and Yan; STOC'11] for combinatorial auctions that is truthful in expectation and guarantees a (1-1/e)-appr…