1.4k citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Microsoft (United States)US40 papers
- Massachusetts Institute of TechnologyUS32 papers
- Microsoft Research (United Kingdom)GB18 papers
- Harvard UniversityUS11 papers
- Cornell UniversityUS10 papers
- University of PennsylvaniaUS10 papers
- Princeton UniversityUS8 papers
- Stanford UniversityUS8 papers
- University of WashingtonUS8 papers
- Hebrew University of JerusalemIL7 papers
- Carnegie Mellon UniversityUS6 papers
- Rutgers, The State University of New JerseyUS6 papers
10 papers · 1 filter
Online Pandora's Boxes and Bandits
Hossein Esfandiari, MohammadTaghi Hajiaghayi, Brendan Lucier +1
We consider online variations of the Pandora's box problem (Weitzman. 1979), a standard model for understanding issues related to the cost of acquiring information for decision-mak…
Efficient Multiparty Interactive Coding for Insertions, Deletions and Substitutions
Ran Gelles, Yael T. Kalai, Govind Ramnarayan
In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop…
Geometric Median in Nearly Linear Time
Michael B. Cohen, Yin Tat Lee, Gary Miller +2
In this paper we provide faster algorithms for solving the geometric median problem: given points in compute a point that minimizes the sum of Euclidean distan…
Faster Eigenvector Computation via Shift-and-Invert Preconditioning
Dan Garber, Elad Hazan, Chi Jin +4
We give faster algorithms and improved sample complexities for estimating the top eigenvector of a matrix -- i.e. computing a unit vector such that …
Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation
Chi Jin, Sham M. Kakade, Cameron Musco +2
We provide faster algorithms and improved sample complexities for approximating the top eigenvector of a matrix. Offline Setting: Given an matrix , we show how to c…
Optimal Algorithms for Testing Closeness of Discrete Distributions
Siu-On Chan, Ilias Diakonikolas, Gregory Valiant +1
We study the question of closeness testing for two discrete distributions. More precisely, given samples from two distributions and over an -element set, we wish to dist…
Maximizing Social Influence in Nearly Optimal Time
Christian Borgs, Michael Brautbar, Jennifer Chayes +1
Diffusion is a fundamental graph process, underpinning such phenomena as epidemic disease contagion and the spread of innovation by word-of-mouth. We address the algorithmic proble…
Analysis of a randomized approximation scheme for matrix multiplication
Daniel Hsu, Sham M. Kakade, Tong Zhang
This note gives a simple analysis of a randomized approximation scheme for matrix multiplication proposed by Sarlos (2006) based on a random rotation followed by uniform column sam…
Multi-Scale Matrix Sampling and Sublinear-Time PageRank Computation
Christian Borgs, Michael Brautbar, Jennifer Chayes +1
A fundamental problem arising in many applications in Web science and social network analysis is, given an arbitrary approximation factor , to output a set of nodes that w…
Approximating Sparsest Cut in Graphs of Bounded Treewidth
Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra
We give the first constant-factor approximation algorithm for Sparsest Cut with general demands in bounded treewidth graphs. In contrast to previous algorithms, which rely on the f…