7k citations
- University of California, Santa BarbaraUS109 papers
- Microsoft Research (United Kingdom)GB50 papers
- ETH ZurichCH46 papers
- University of California, BerkeleyUS45 papers
- University of Maryland, College ParkUS43 papers
- Carnegie Mellon UniversityUS41 papers
- Stanford UniversityUS39 papers
- University of WashingtonUS37 papers
- Cornell UniversityUS32 papers
- Princeton UniversityUS32 papers
- California Institute of TechnologyUS28 papers
- Microsoft Research New York City (United States)25 papers
6 papers · 2 filters
FPTAS for #BIS with Degree Bounds on One Side
Jingcheng Liu, Pinyan Lu
Counting the number of independent sets for a bipartite graph (#BIS) plays a crucial role in the study of approximate counting. It has been conjectured that there is no fully polyn…
Computing Classic Closeness Centrality, at Scale
Edith Cohen, Daniel Delling, Thomas Pajor +1
Closeness centrality, first considered by Bavelas (1948), is an importance measure of a node in a network which is based on the distances from the node to all other nodes. The clas…
Sketch-based Influence Maximization and Computation: Scaling up with Guarantees
Edith Cohen, Daniel Delling, Thomas Pajor +1
Propagation of contagion through networks is a fundamental process. It is used to model the spread of information, influence, or a viral infection. Diffusion patterns can be specif…
Spectral Approaches to Nearest Neighbor Search
Amirali Abdullah, Alexandr Andoni, Ravindran Kannan +1
We study spectral algorithms for the high-dimensional Nearest Neighbor Search problem (NNS). In particular, we consider a semi-random setting where a dataset in …
LP-Based Algorithms for Capacitated Facility Location
Hyung-Chan An, Mohit Singh, Ola Svensson
Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by t…
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Boaz Barak, Jonathan A. Kelner, David Steurer
We give a new approach to the dictionary learning (also known as "sparse coding") problem of recovering an unknown matrix (for ) from examples of the form…