21 citations · 101 across the 20 of their papers we have counts for
9 papers · 1 filter
Greedy and Local Ratio Algorithms in the MapReduce Model
Nicholas J. A. Harvey, Christopher Liaw, Paul Liu
MapReduce has become the de facto standard model for designing distributed algorithms to process big data on a cluster. There has been considerable research on designing efficient…
Computing the Independence Polynomial: from the Tree Threshold down to the Roots
Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák
We study an algorithm for approximating the multivariate independence polynomial , with negative and complex arguments, an object that has strong connections to comb…
An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles
Nicholas Harvey, Jan Vondrak
The Lovasz Local Lemma is a seminal result in probabilistic combinatorics. It gives a sufficient condition on a probability space and a collection of events for the existence of an…
Pipage Rounding, Pessimistic Estimators and Matrix Concentration
Nicholas J. A. Harvey, Neil Olver
Pipage rounding is a dependent random sampling technique that has several interesting properties and diverse applications. One property that has been particularly useful is negativ…
Submodular Functions: Learnability, Structure, and Optimization
Maria-Florina Balcan, Nicholas J. A. Harvey
Submodular functions are discrete functions that model laws of diminishing returns and enjoy numerous algorithmic applications. They have been used in many areas, including combina…
Graph Sparsification by Edge-Connectivity and Random Spanning Trees
Wai Shing Fung, Nicholas J. A. Harvey
We present new approaches to constructing graph sparsifiers --- weighted subgraphs for which every cut has the same value as the original graph, up to a factor of . Our…