6 citations · 33 across the 33 of their papers we have counts for
46 papers
A note on rounding fractional matchings with constant-factor strong negative correlation
David G. Harris
We describe new dependent-rounding algorithms for bipartite graphs. Given a fractional matching of graph , the algorithms return an integral solution suc…
The singleton hypergraph is extremal for the Isolation Lemma
Vance Faber, David G. Harris
Let be an inclusion-free hypergraph on vertices. A weight assignment is isolating if there is a unique edge whose weight is m…
The Dirichlet Mechanism for rounding with strong negative correlation, with applications
David G. Harris, George Z. Li, Nitya Raju +1
Many optimization and scheduling problems can be abstracted in terms of a bipartite ``assignment graph" , where the goal is to select exactly one edge for each r…
Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time
David G. Harris
We describe a new dependent-rounding algorithmic framework for bipartite graphs. Given a fractional assignment of values to edges of graph , the algorit…
Simple and efficient four-cycle counting on sparse graphs
Paul Burkhardt, David G. Harris
We consider the problem of counting 4-cycles () in an undirected graph of vertices and edges (in bipartite graphs, 4-cycles are also often referred to as $\textit{…
A faster algorithm for Vertex Cover parameterized by solution size
David G. Harris, N. S. Narayanaswamy
We describe a new algorithm for vertex cover with runtime , where is the size of the desired solution and hides polynomial factors in the input size. This…
Algorithms for matrix multiplication via sampling and opportunistic matrix multiplication
David G. Harris
Karppa & Kaski (2019) proposed a novel ``broken" or ``opportunistic" matrix multiplication algorithm, based on a variant of Strassen's algorithm, and used this to develop new algor…
Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture
Nikhil Bansal, David G. Harris
A classic conjecture of Füredi, Kahn and Seymour (1993) states that given any hypergraph with non-negative edge weights , there exists a matching such that $\sum_{e \in M…
On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition
David G. Harris, Hsin-Hao Su, Hoa T. Vu
Given a graph with arboricity , we study the problem of decomposing the edges of into disjoint forests in the distributed LOCAL model. Barenboim and Elkin…
A new notion of commutativity for the algorithmic Lovász Local Lemma
David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov
The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthr…
Stochastic Optimization and Learning for Two-Stage Supplier Problems
Brian Brubach, Nathaniel Grammel, David G. Harris +3
The main focus of this paper is radius-based (supplier) clustering in the two-stage stochastic setting with recourse, where the inherent stochasticity of the model comes in the for…
Optimal Bounds for the -cut Problem
Anupam Gupta, David G. Harris, Euiwoong Lee +1
In the -cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into connected components. Algorithms of Karger \& Stein can s…
Deterministic algorithms for the Lovasz Local Lemma: simpler, more general, and more parallel
David G. Harris
The Lovász Local Lemma (LLL) is a keystone principle in probability theory, guaranteeing the existence of configurations which avoid a collection of "bad" events which…
Algorithms for weighted independent transversals and strong colouring
Alessandra Graf, David G. Harris, Penny Haxell
An independent transversal (IT) in a graph with a given vertex partition is an independent set consisting of one vertex in each partition class. Several sufficient conditions are k…
Parameter estimation for integer-valued Gibbs distributions
David G. Harris, Vladimir Kolmogorov
A central problem in computational statistics is to convert a procedure for sampling combinatorial from an objects into a procedure for counting those objects, and vice versa. Weco…
Exponentially Faster Massively Parallel Maximal Matching
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, however, we still have a far…
The Combinatorial Data Fusion Problem in Conflicted-supervised Learning
R. W. R. Darling, David G. Harris, Dev R. Phulara +1
The best merge problem in industrial data science generates instances where disparate data sources place incompatible relational structures on the same set of objects. Graph ve…
Approximation algorithms for stochastic clustering
David G. Harris, Shi Li, Thomas Pensyl +2
We consider stochastic settings for clustering, and develop provably-good approximation algorithms for a number of these notions. These algorithms yield better approximation ratios…
Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
David G. Harris
We describe approximation algorithms in Linial's classic LOCAL model of distributed computing to find maximum-weight matchings in a hypergraph of rank . Our main result is a det…
Derandomizing the Lovasz Local Lemma via log-space statistical tests
David G. Harris
The Lovász Local Lemma (LLL) is a keystone principle in probability theory, guaranteeing the existence of configurations which avoid a collection of "bad" events which…
Bounds and algorithms for graph trusses
Paul Burkhardt, Vance Faber, David G. Harris
The -truss, introduced by Cohen (2005), is a graph where every edge is incident to at least triangles. This is a relaxation of the clique. It has proved to be a useful tool…
Deterministic parallel algorithms for bilinear objective functions
David G. Harris
Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low independence. A series of papers, begi…
On Derandomizing Local Distributed Algorithms
Mohsen Ghaffari, David G. Harris, Fabian Kuhn
The gap between the known randomized and deterministic local distributed algorithms underlies arguably the most fundamental and central open question in distributed graph algorithm…
A Lottery Model for Center-type Problems With Outliers
David G. Harris, Thomas Pensyl, Aravind Srinivasan +1
In this paper, we give tight approximation algorithms for the -center and matroid center problems with outliers. Unfairness arises naturally in this setting: certain clients cou…