David G. Harris

Publication Activity (10 Years)

Years Active: 2008-2023
Publications (10 Years): 84

Top Topics

Independent Set

Parallel Algorithm

Johnson Lindenstrauss

Top Venues

ACM Trans. Algorithms

Random Struct. Algorithms

Publications

Paul Burkhardt, David G. Harris
Simple and efficient four-cycle counting on sparse graphs. CoRR (2023)
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
Exponentially Faster Massively Parallel Maximal Matching. J. ACM 70 (5) (2023)
David G. Harris, Hsin-Hao Su, Hoa T. Vu
On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition. SIAM J. Discret. Math. 37 (2) (2023)
David G. Harris
Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel. Random Struct. Algorithms 63 (3) (2023)
David G. Harris
Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time. CoRR (2023)
Nikhil Bansal, David G. Harris
Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture. Random Struct. Algorithms 62 (1) (2023)
David G. Harris, Vladimir Kolmogorov
Parameter Estimation for Gibbs Distributions. ICALP (2023)
David G. Harris
Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix Multiplication. ESA (2023)
Anupam Gupta, David G. Harris, Euiwoong Lee, Jason Li
-cut Problem. J. ACM 69 (1) (2022)
David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh
Dependent randomized rounding for clustering and partition systems with knapsack constraints. J. Mach. Learn. Res. 23 (2022)
Alessandra Graf, David G. Harris, Penny Haxell
Algorithms for Weighted Independent Transversals and Strong Colouring. ACM Trans. Algorithms 18 (1) (2022)
David G. Harris
Deterministic algorithms for the Lovász Local Lemma: simpler, more general, and more parallel. SODA (2022)
David G. Harris, N. S. Narayanaswamy
A faster algorithm for Vertex Cover parameterized by solution size. CoRR (2022)
Alessandra Graf, David G. Harris, Penny Haxell
Algorithms for weighted independent transversals and strong colouring. SODA (2021)
David G. Harris
Improved algorithms for Boolean matrix multiplication via opportunistic matrix multiplication. CoRR (2021)
David G. Harris
Oblivious Resampling Oracles and Parallel Algorithms for the Lopsided Lovász Local Lemma. ACM Trans. Algorithms 17 (1) (2021)
Brian Brubach, Nathaniel Grammel, David G. Harris, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti
Approximating Two-Stage Stochastic Supplier Problems. APPROX-RANDOM (2021)
David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov
A New Notion of Commutativity for the Algorithmic Lovász Local Lemma. APPROX-RANDOM (2021)
David G. Harris, Hsin-Hao Su, Hoa T. Vu
On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition. PODC (2021)
Antares Chen, David G. Harris, Aravind Srinivasan
Partial resampling to approximate covering integer programs. Random Struct. Algorithms 58 (1) (2021)
Nikhil Bansal, David G. Harris
Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture. CoRR (2020)
Brian Brubach, Nathaniel Grammel, David G. Harris, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti
Approximation Algorithms for Radius-Based, Two-Stage Stochastic Clustering Problems with Budget Constraints. CoRR (2020)
David G. Harris
New bounds for the Moser-Tardos distribution. Random Struct. Algorithms 57 (1) (2020)
David G. Harris
Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs. SIAM J. Comput. 49 (4) (2020)
David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh
Dependent randomized rounding for clustering and partition systems with knapsack constraints. AISTATS (2020)
Paul Burkhardt, Vance Faber, David G. Harris
Bounds and algorithms for graph trusses. J. Graph Algorithms Appl. 24 (3) (2020)
David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov
A new notion of commutativity for the algorithmic Lovász Local Lemma. CoRR (2020)
Anupam Gupta, David G. Harris, Euiwoong Lee, Jason Li
Optimal Bounds for the k-cut Problem. CoRR (2020)
David G. Harris, Hsin-Hao Su, Hoa T. Vu
On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition. CoRR (2020)
David G. Harris, Vladimir Kolmogorov
Parameter estimation for Gibbs distributions. CoRR (2020)
David G. Harris
Deterministic Parallel Algorithms for Bilinear Objective Functions. Algorithmica 81 (3) (2019)
David G. Harris, Shi Li, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh
Approximation Algorithms for Stochastic Clustering. J. Mach. Learn. Res. 20 (2019)
David G. Harris, Aravind Srinivasan
The Moser-Tardos Framework with Partial Resampling. J. ACM 66 (5) (2019)
David G. Harris
Some Results on Chromatic Number as a Function of Triangle Count. SIAM J. Discret. Math. 33 (1) (2019)
David G. Harris
Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set. ACM Trans. Algorithms 15 (3) (2019)
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
Exponentially Faster Massively Parallel Maximal Matching. CoRR (2019)
Alessandra Graf, David G. Harris, Penny Haxell
Algorithms for weighted independent transversals and strong colouring. CoRR (2019)
Vance Faber, David G. Harris
Edge-coloring linear hypergraphs with medium-sized edges. Random Struct. Algorithms 55 (1) (2019)
David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh
A Lottery Model for Center-Type Problems With Outliers. ACM Trans. Algorithms 15 (3) (2019)
David G. Harris
Deterministic algorithms for the Lovasz Local Lemma: simpler, more general, and more parallel. CoRR (2019)
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
Exponentially Faster Massively Parallel Maximal Matching. FOCS (2019)
David G. Harris
Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs. FOCS (2019)
David G. Harris
Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma. SODA (2019)
David G. Harris
Distributed approximation algorithms for maximum matching in graphs and hypergraphs. CoRR (2018)
David G. Harris, Shi Li, Aravind Srinivasan, Khoa Trinh, Thomas W. Pensyl
Approximation algorithms for stochastic clustering. NeurIPS (2018)
Mohsen Ghaffari, David G. Harris, Fabian Kuhn
On Derandomizing Local Distributed Algorithms. FOCS (2018)
David G. Harris, Shi Li, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh
Approximation algorithms for stochastic clustering. CoRR (2018)
David G. Harris
Deterministic Parallel Algorithms for Fooling Polylogarithmic Juntas and the Lovász Local Lemma. ACM Trans. Algorithms 14 (4) (2018)
Paul Burkhardt, Vance Faber, David G. Harris
Bounds and algorithms for k-truss. CoRR (2018)
David G. Harris
Derandomized concentration bounds for polynomials, and hypergraph maximal independent set. SODA (2018)
David G. Harris, Johannes Schneider, Hsin-Hao Su
Distributed (Δ +1)-Coloring in Sublogarithmic Rounds. J. ACM 65 (4) (2018)
David G. Harris, Aravind Srinivasan
Improved bounds and algorithms for graph cuts and network reliability. Random Struct. Algorithms 52 (1) (2018)
David G. Harris
Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovász Local Lemma. SODA (2017)
David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh
Symmetric Randomized Dependent Rounding. CoRR (2017)
David G. Harris
Deterministic parallel algorithms for bilinear objective functions. CoRR (2017)
David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh
A Lottery Model for Center-Type Problems with Outliers. APPROX-RANDOM (2017)
David G. Harris
Parallel algorithms for the Lopsided Lovász Local Lemma. CoRR (2017)
David G. Harris, Aravind Srinivasan
Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution. ACM Trans. Algorithms 13 (3) (2017)
Mohsen Ghaffari, David G. Harris, Fabian Kuhn
On Derandomizing Local Distributed Algorithms. CoRR (2017)
David G. Harris, Aravind Srinivasan
A Constructive Lovász Local Lemma for Permutations. Theory Comput. 13 (1) (2017)
David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, Khoa Trinh
A Lottery Model for Center-type Problems With Outliers. CoRR (2017)
Bernhard Haeupler, David G. Harris
Parallel Algorithms and Concentration Bounds for the Lovász Local Lemma via Witness DAGs. ACM Trans. Algorithms 13 (4) (2017)
Bernhard Haeupler, David G. Harris
Parallel algorithms and concentration bounds for the Lovász Local Lemma via witness-DAGs. SODA (2017)
David G. Harris
Lopsidependency in the Moser-Tardos Framework: Beyond the Lopsided Lovász Local Lemma. ACM Trans. Algorithms 13 (1) (2016)
David G. Harris
The Moser-Tardos lopsidependency criterion can be stronger than Shearer's criterion. CoRR (2016)
David G. Harris, Johannes Schneider, Hsin-Hao Su
Distributed (Δ+1)-Coloring in Sublogarithmic Rounds. CoRR (2016)
Ioana Oriana Bercea, Navin Goyal, David G. Harris, Aravind Srinivasan
On Computing Maximal Independent Sets of Hypergraphs in Parallel. ACM Trans. Parallel Comput. 3 (1) (2016)
David G. Harris
Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovasz Local Lemma. CoRR (2016)
David G. Harris, Aravind Srinivasan
A constructive algorithm for the LLL on permutations. CoRR (2016)
David G. Harris, Aravind Srinivasan
A note on near-optimal coloring of shift hypergraphs. Random Struct. Algorithms 48 (1) (2016)
David G. Harris, Ehab Morsy, Gopal Pandurangan, Peter Robinson, Aravind Srinivasan
Efficient computation of sparse structures. Random Struct. Algorithms 49 (2) (2016)
Antares Chen, David G. Harris, Aravind Srinivasan
Partial Resampling to Approximate Covering Integer Programs. SODA (2016)
David G. Harris, Johannes Schneider, Hsin-Hao Su
Distributed (∆+1)-coloring in sublogarithmic rounds. STOC (2016)
David G. Harris
Improved parallel algorithms for hypergraph maximal independent set. CoRR (2016)
David G. Harris, Aravind Srinivasan
Improved bounds and algorithms for graph cuts and network reliability. CoRR (2016)
David G. Harris
Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovasz Local Lemma. CoRR (2016)
David G. Harris
New bounds for the Moser-Tardos distribution: Beyond the Lovasz Local Lemma. CoRR (2016)
David G. Harris, Aravind Srinivasan
Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution. SODA (2016)
Bernhard Haeupler, David G. Harris
Improved bounds and parallel algorithms for the Lovasz Local Lemma. CoRR (2015)
David G. Harris, Francis Sullivan
Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs. APPROX-RANDOM (2015)
David Conlon, Jacob Fox, William I. Gasarch, David G. Harris, Douglas Ulrich, Samuel Zbarsky
Distinct Volume Subsets. SIAM J. Discret. Math. 29 (1) (2015)
Antares Chen, David G. Harris, Aravind Srinivasan
Partial Resampling to Approximate Covering Integer Programs. CoRR (2015)
David G. Harris, Aravind Srinivasan
Algorithmic and enumerative aspects of the Moser-Tardos distribution. CoRR (2015)
David G. Harris
Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovász Local Lemma. SODA (2015)
David G. Harris, Aravind Srinivasan
A constructive algorithm for the Lovász Local Lemma on permutations. SODA (2014)
David G. Harris, Aravind Srinivasan
The Moser-Tardos Framework with Partial Resampling. CoRR (2014)
Ioana Oriana Bercea, Navin Goyal, David G. Harris, Aravind Srinivasan
On computing maximal independent sets of hypergraphs in parallel. SPAA (2014)
David G. Harris, Aravind Srinivasan
Improved bounds and algorithms for graph cuts and network reliability. SODA (2014)
David G. Harris, Francis Sullivan, Isabel Beichl
Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial. Algorithmica 68 (4) (2014)
Ioana Oriana Bercea, Navin Goyal, David G. Harris, Aravind Srinivasan
On Computing Maximal Independent Sets of Hypergraphs in Parallel. CoRR (2014)
David Conlon, Jacob Fox, William I. Gasarch, David G. Harris, Douglas Ulrich, Sam Zbarsky
Distinct volume subsets. CoRR (2014)
David G. Harris, Manish Purohit
Improved algorithms and analysis for the laminar matroid secretary problem CoRR (2013)
David G. Harris, Ehab Morsy, Gopal Pandurangan, Peter Robinson, Aravind Srinivasan
Efficient Computation of Balanced Structures. ICALP (2) (2013)
David G. Harris, Aravind Srinivasan
Constraint satisfaction, packet routing, and the lovasz local lemma. STOC (2013)
David G. Harris, Aravind Srinivasan
The Moser-Tardos Framework with Partial Resampling. FOCS (2013)
David G. Harris
Critique of the related-key attack concept. Des. Codes Cryptogr. 59 (1-3) (2011)
David G. Harris, Francis Sullivan, Isabel Beichl
Linear algebra and sequential importance sampling for network reliability. WSC (2011)
David G. Harris
Simultaneous field divisions: an extension of Montgomery's trick. IACR Cryptol. ePrint Arch. 2008 (2008)