David G. Harris

According to our database, David G. Harris authored at least 60 papers between 2008 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix Multiplication.

David G. Harris

Algorithmica, September, 2024

A Faster Algorithm for Vertex Cover Parameterized by Solution Size.

David G. Harris, N. S. Narayanaswamy

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time.

David G. Harris

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel.

David G. Harris

Random Struct. Algorithms, October, 2023

Exponentially Faster Massively Parallel Maximal Matching.

Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris

J. ACM, October, 2023

On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition.

David G. Harris, Hsin-Hao Su, Hoa T. Vu

SIAM J. Discret. Math., June, 2023

Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture.

Nikhil Bansal, David G. Harris

Random Struct. Algorithms, 2023

Simple and efficient four-cycle counting on sparse graphs.

Paul Burkhardt, David G. Harris

CoRR, 2023

Parameter Estimation for Gibbs Distributions.

David G. Harris, Vladimir Kolmogorov

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Algorithms for Weighted Independent Transversals and Strong Colouring.

Alessandra Graf, David G. Harris, Penny Haxell

ACM Trans. Algorithms, 2022

Dependent randomized rounding for clustering and partition systems with knapsack constraints.

David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh

J. Mach. Learn. Res., 2022

Optimal Bounds for the <i>k</i>-cut Problem.

Anupam Gupta, David G. Harris, Euiwoong Lee, Jason Li

J. ACM, 2022

2021

Oblivious Resampling Oracles and Parallel Algorithms for the Lopsided Lovász Local Lemma.

David G. Harris

ACM Trans. Algorithms, 2021

Partial resampling to approximate covering integer programs.

Antares Chen, David G. Harris, Aravind Srinivasan

Random Struct. Algorithms, 2021

Improved algorithms for Boolean matrix multiplication via opportunistic matrix multiplication.

David G. Harris

CoRR, 2021

A New Notion of Commutativity for the Algorithmic Lovász Local Lemma.

David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov

Proceedings of the Approximation, 2021

Approximating Two-Stage Stochastic Supplier Problems.

Brian Brubach, Nathaniel Grammel, David G. Harris, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti

Proceedings of the Approximation, 2021

2020

Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs.

David G. Harris

SIAM J. Comput., 2020

New bounds for the Moser-Tardos distribution.

David G. Harris

Random Struct. Algorithms, 2020

Bounds and algorithms for graph trusses.

Paul Burkhardt, Vance Faber, David G. Harris

J. Graph Algorithms Appl., 2020

Approximation Algorithms for Radius-Based, Two-Stage Stochastic Clustering Problems with Budget Constraints.

Brian Brubach, Nathaniel Grammel, David G. Harris, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti

CoRR, 2020

Optimal Bounds for the k-cut Problem.

Anupam Gupta, David G. Harris, Euiwoong Lee, Jason Li

CoRR, 2020

2019

A Lottery Model for Center-Type Problems With Outliers.

David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh

ACM Trans. Algorithms, 2019

Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set.

David G. Harris

ACM Trans. Algorithms, 2019

Some Results on Chromatic Number as a Function of Triangle Count.

David G. Harris

SIAM J. Discret. Math., 2019

Edge-coloring linear hypergraphs with medium-sized edges.

Vance Faber, David G. Harris

Random Struct. Algorithms, 2019

Approximation Algorithms for Stochastic Clustering.

David G. Harris, Shi Li, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh

J. Mach. Learn. Res., 2019

The Moser-Tardos Framework with Partial Resampling.

David G. Harris, Aravind Srinivasan

J. ACM, 2019

Deterministic Parallel Algorithms for Bilinear Objective Functions.

David G. Harris

Algorithmica, 2019

2018

Deterministic Parallel Algorithms for Fooling Polylogarithmic Juntas and the Lovász Local Lemma.

David G. Harris

ACM Trans. Algorithms, 2018

Improved bounds and algorithms for graph cuts and network reliability.

David G. Harris, Aravind Srinivasan

Random Struct. Algorithms, 2018

Distributed (Δ +1)-Coloring in Sublogarithmic Rounds.

David G. Harris, Johannes Schneider, Hsin-Hao Su

J. ACM, 2018

Distributed approximation algorithms for maximum matching in graphs and hypergraphs.

David G. Harris

CoRR, 2018

Bounds and algorithms for k-truss.

Paul Burkhardt, Vance Faber, David G. Harris

CoRR, 2018

On Derandomizing Local Distributed Algorithms.

Mohsen Ghaffari, David G. Harris, Fabian Kuhn

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

A Constructive Lovász Local Lemma for Permutations.

David G. Harris, Aravind Srinivasan

Theory Comput., 2017

Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution.

David G. Harris, Aravind Srinivasan

ACM Trans. Algorithms, 2017

Parallel Algorithms and Concentration Bounds for the Lovász Local Lemma via Witness DAGs.

Bernhard Haeupler, David G. Harris

ACM Trans. Algorithms, 2017

Symmetric Randomized Dependent Rounding.

David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh

CoRR, 2017

Parallel algorithms for the Lopsided Lovász Local Lemma.

David G. Harris

CoRR, 2017

2016

On Computing Maximal Independent Sets of Hypergraphs in Parallel.

Ioana Oriana Bercea, Navin Goyal, David G. Harris, Aravind Srinivasan

ACM Trans. Parallel Comput., 2016

Lopsidependency in the Moser-Tardos Framework: Beyond the Lopsided Lovász Local Lemma.

David G. Harris

ACM Trans. Algorithms, 2016

A note on near-optimal coloring of shift hypergraphs.

David G. Harris, Aravind Srinivasan

Random Struct. Algorithms, 2016

Efficient computation of sparse structures.

David G. Harris, Ehab Morsy, Gopal Pandurangan, Peter Robinson, Aravind Srinivasan

Random Struct. Algorithms, 2016

A constructive algorithm for the LLL on permutations.

David G. Harris, Aravind Srinivasan

CoRR, 2016

New bounds for the Moser-Tardos distribution: Beyond the Lovasz Local Lemma.

David G. Harris

CoRR, 2016

The Moser-Tardos lopsidependency criterion can be stronger than Shearer's criterion.

David G. Harris

CoRR, 2016

Improved parallel algorithms for hypergraph maximal independent set.

David G. Harris

CoRR, 2016

Distributed (∆+1)-coloring in sublogarithmic rounds.

David G. Harris, Johannes Schneider, Hsin-Hao Su

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Distinct Volume Subsets.

David Conlon, Jacob Fox, William I. Gasarch, David G. Harris, Douglas Ulrich, Samuel Zbarsky

SIAM J. Discret. Math., 2015

Improved bounds and parallel algorithms for the Lovasz Local Lemma.

Bernhard Haeupler, David G. Harris

CoRR, 2015

Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs.

David G. Harris, Francis Sullivan

Proceedings of the Approximation, 2015

2014

Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial.

David G. Harris, Francis Sullivan, Isabel Beichl

Algorithmica, 2014

A constructive algorithm for the Lovász Local Lemma on permutations.

David G. Harris, Aravind Srinivasan

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013

Improved algorithms and analysis for the laminar matroid secretary problem

David G. Harris, Manish Purohit

CoRR, 2013

Constraint satisfaction, packet routing, and the lovasz local lemma.

David G. Harris, Aravind Srinivasan

Proceedings of the Symposium on Theory of Computing Conference, 2013

Efficient Computation of Balanced Structures.

David G. Harris, Ehab Morsy, Gopal Pandurangan, Peter Robinson, Aravind Srinivasan

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2011

Critique of the related-key attack concept.

David G. Harris

Des. Codes Cryptogr., 2011

Linear algebra and sequential importance sampling for network reliability.

David G. Harris, Francis Sullivan, Isabel Beichl

Proceedings of the Winter Simulation Conference 2011, 2011

2008

Simultaneous field divisions: an extension of Montgomery's trick.

David G. Harris

IACR Cryptol. ePrint Arch., 2008