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
On Sketching Quadratic Forms
Alexandr Andoni, Jiecao Chen, Robert Krauthgamer +3
We undertake a systematic study of sketching a quadratic form: given an matrix , create a succinct sketch which can produce (without further access…
Input Sparsity and Hardness for Robust Subspace Approximation
Kenneth L. Clarkson, David P. Woodruff
In the subspace approximation problem, we seek a k-dimensional subspace F of R^d that minimizes the sum of p-th powers of Euclidean distances to a given set of n points a_1, ..., a…
Applications of Uniform Sampling: Densest Subgraph and Beyond
Hossein Esfandiari, MohammadTaghi Hajiaghayi, David P. Woodruff
Recently [Bhattacharya et al., STOC 2015] provide the first non-trivial algorithm for the densest subgraph problem in the streaming model with additions and deletions to its edges,…
Optimal Principal Component Analysis in Distributed and Streaming Models
Christos Boutsidis, David P. Woodruff, Peilin Zhong
We study the Principal Component Analysis (PCA) problem in the distributed and streaming models of computation. Given a matrix a rank parameter $k < rank(A)…
Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions
Vitaly Feldman, Jan Vondrak
Submodular and fractionally subadditive (or equivalently XOS) functions play a fundamental role in combinatorial optimization, algorithmic game theory and machine learning. Motivat…
Sorting and Selection with Imprecise Comparisons
Miklos Ajtai, Vitaly Feldman, Avinatan Hassidim +1
We consider a simple model of imprecise comparisons: there exists some such that when a subject is given two elements to compare, if the values of those elements (as perceive…