David G. Harris

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

Collaborative distances:

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

2025

Simple parallel estimation of the partition ratio for Gibbs distributions.

David G. Harris, Vladimir Kolmogorov

CoRR, May, 2025

Improved Parallel Derandomization via Finite Automata with Applications.

Jeff Giliberti, David G. Harris

Proceedings of the 33rd Annual European Symposium on Algorithms, 2025

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

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

Algorithms for Matrix Multiplication via Sampling and Opportunistic Matrix Multiplication.

David G. Harris

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

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

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

J. ACM, 2022

Deterministic algorithms for the Lovász Local Lemma: simpler, more general, and more parallel.

David G. Harris

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

2021

Improved algorithms for Boolean matrix multiplication via opportunistic matrix multiplication.

David G. Harris

CoRR, 2021

Algorithms for weighted independent transversals and strong colouring.

Alessandra Graf, David G. Harris, Penny Haxell

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

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

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

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 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

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

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

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

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

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

Deterministic Parallel Algorithms for Bilinear Objective Functions.

David G. Harris

Algorithmica, 2019

Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma.

David G. Harris

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

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

David G. Harris

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Exponentially Faster Massively Parallel Maximal Matching.

Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

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

Derandomized concentration bounds for polynomials, and hypergraph maximal independent set.

David G. Harris

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Approximation algorithms for stochastic clustering.

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

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 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

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

Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovász Local Lemma.

David G. Harris

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Parallel algorithms and concentration bounds for the Lovász Local Lemma via witness-DAGs.

Bernhard Haeupler, David G. Harris

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

A Lottery Model for Center-Type Problems with Outliers.

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

Proceedings of the Approximation, 2017

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

Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution.

David G. Harris, Aravind Srinivasan

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Partial Resampling to Approximate Covering Integer Programs.

Antares Chen, David G. Harris, Aravind Srinivasan

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Algorithms and Generalizations for the Lovasz Local Lemma.

David G. Harris

PhD thesis, 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

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

David G. Harris

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

On computing maximal independent sets of hypergraphs in parallel.

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

Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 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

Improved bounds and algorithms for graph cuts and network reliability.

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

The Moser-Tardos Framework with Partial Resampling.

David G. Harris, Aravind Srinivasan

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 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