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
5 papers · 2 filters
The Noisy Power Method: A Meta Algorithm with Applications
Moritz Hardt, Eric Price
We provide a new robust convergence analysis of the well-known power method for computing the dominant singular vectors of a matrix that we call the noisy power method. Our result…
Multiway Cut, Pairwise Realizable Distributions, and Descending Thresholds
Ankit Sharma, Jan Vondrák
We design new approximation algorithms for the Multiway Cut problem, improving the previously known factor of 1.32388 [Buchbinder et al., 2013]. We proceed in three steps. First, w…
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
Vitaly Feldman, Jan Vondrak
We investigate the approximability of several classes of real-valued functions by functions of a small number of variables ({\em juntas}). Our main results are tight bounds on the…
When Distributed Computation is Communication Expensive
David P. Woodruff, Qin Zhang
We consider a number of fundamental statistical and graph problems in the message-passing model, where we have machines (sites), each holding a piece of data, and the machines…
Principal Component Analysis and Higher Correlations for Distributed Data
Ravindran Kannan, Santosh Vempala, David Woodruff
We consider algorithmic problems in the setting in which the input data has been partitioned arbitrarily on many servers. The goal is to compute a function of all the data, and the…