Publications

Miscellaneous algorithms

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

• "Improved algorithms for Boolean matrix multiplication via sampling and opportunistic matrix multiplication." To appear in Algorithmica. (Originally appeared in ESA 2023.)

• "Parameter estimation for Gibbs distributions." With V. Kolmogorov. To appear in ACM Transactions on Algorithms (Originally appeared in ICALP 2023.)

Parallel/distributed graph algorithms

• "Exponentially faster massively parallel maximal matching." With S. Behnezhad and M. Hajiaghayi. Journal of the ACM 70(5), Article #34  (2023) (Originally appeared in FOCS 2019)

• "On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition". With H. Su and H. Vu. SIAM Journal on Discrete Mathematics 37(2), pp. 800-830 (2023) (Originally appeared in PODC 2021).

• "Distributed local approximation algorithms for maximum matching in graphs and hypergraphs". SIAM Journal on Computing 49(4), pp. 711-746 (2020) (Originally appeared in FOCS 2019)

• "Derandomized concentration bounds for polynomials, and hypergraph maximal independent set". ACM Transactions on Algorithms 15(3),  Article #43 (2019) (Originally appeared in SODA 2018).

• "On derandomizing local distributed algorithms" With F. Kuhn and M. Ghaffari. FOCS 2018

• "Distributed (Δ+1)-coloring in sublogarithmic rounds"  With J. Schneider and H. Su. Journal of the ACM 65(4), Article #19 (2018) (Originally appeared in STOC 2016.)

• "On computing maximal independent sets of hypergraphs in parallel" With I. Bercea, N. Goyal, A. Srinivasan. ACM Transactions on Parallel Computing 3(1), Article #5 (2016) (originally appeared in SPAA 2014)

• “Efficient computation of sparse structures” With E. Morsy, G. Pandurangan, P. Robinson, A. Srinivasan.  Random Structures & Algorithms 49(2), pp. 322-344 (2016) (originally appeared in ICALP 2013)

Clustering

• "Stochastic Optimization and Learning for Two-Stage Supplier Problems."  With B. Brubach, N. Grammel, A. Srinivasan, L. Tsepenekas, A. Vulikanti. To appear in ACM Transactions on Probabilistic Machine Learning. (Originally appeared in APPROX 2021)

• "Dependent randomized rounding for clustering and partition systems with knapsack constraints." With T. Pensyl, A. Srinivasan, and K. Trinh. Journal of Machine Learning Research 23(81), pp. 1-41 (2022)    (Originally appeared in AISTATS 2020) (NOTE: the version published on JMLR has a small error in Proposition 25. The arxiv version, linked here, is correct.)

• "Approximation algorithms for stochastic clustering". With S. Li, T. Pensyl, A. Srinivasan, K. Trinh. Journal of Machine Learning Research 20(153), pp. 1-33 (2019)  (originally appeared in NeurIPS 2018). (NOTE: the version published on JMLR has an error. The arxiv version, linked here, is correct)

• "A lottery model for center-type problems with outliers." With T. Pensyl, A. Srinivasan, K. Trinh. ACM Transactions on Algorithms 15(3), Article #36 (2019) (originally appeared in APPROX 2017)

The Lovász Local Lemma and its Algorithms

• "Deterministic algorithms for the Lovasz Local Lemma: simpler, more general, and more parallel".  Random Structures & Algorithms 63(3), pp. 716-752 (2023)  (Originally appeared in SODA 2022)

• "Comparison of two convergence criteria for the variable-assignment Lopsided Lovasz Local Lemma". Electronic Journal of Combinatorics 29(4), #P4.10 (2022)

• "A new notion of commutativity for the algorithmic Lovász Local Lemma". With F. Iliopoulos and V. Kolmogorov. RANDOM 2021.

• "Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma".  ACM Transactions on Algorithms 17(1), Article #1 (2021) (Originally appeared in SODA 2019)

• "Partial resampling to approximate covering integer programs." With A. Chen and A. Srinivasan.  Random Structures & Algorithms 58(1), pp. 68-93 (2021) (Originally appeared in SODA 2016)

• "New bounds for the Moser-Tardos distribution." Random Structures & Algorithms 57(1), pp. 97-131 (2020)

•  “The Moser-Tardos framework with partial resampling.” With A. Srinivasan. Journal of the ACM 66(5), Article #36 (2019) (Extended version of paper from FOCS 2013)

•  "A constructive Lovász Local Lemma for permutations" With A. Srinivasan. Theory of Computing 13(17), pp. 1-41 (2017) (Originally appeared in SODA 2014)

•  "Algorithmic and enumerative aspects of the Moser-Tardos distribution." With A. Srinivasan. ACM Transactions on Algorithms 13(3), Article #33 (2017) (Originally appeared in SODA 2016)

•  "Parallel algorithms and concentration bounds for the Lovász Local Lemma via witness-DAGs" With B. Haeupler. ACM Transaction on Algorithms 13(4), Article #53 (2017) (Originally appeared in SODA 2017)

• "Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovász Local Lemma" ACM Transactions on Algorithms 13(1), Article #17 (2016) (Originally appeared in SODA 2015)

• "Algorithms and Generalizations for the Lovász Local Lemma" Doctoral Thesis. 2015

•  “Constraint satisfaction, packet routing, and the Lovász Local Lemma”. With A. Srinivasan.  STOC 2013

Derandomization

• "Deterministic algorithms for the Lovasz Local Lemma: simpler, more general, and more parallel". Random Structures & Algorithms 63(3), pp. 716-752 (2023)  (Originally appeared in SODA 2022)

• "On derandomizing local distributed algorithms" With F. Kuhn and M. Ghaffari. FOCS 2018

• "Derandomized concentration bounds for polynomials, and hypergraph maximal independent set". ACM Transactions on Algorithms 15(3),  Article #43 (2019) (Originally appeared in SODA 2018).

• "Deterministic parallel algorithms for bilinear objective functions". Algorithmica 81(3), pp. 1288-1318 (2019)

• "Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovász Local Lemma"  ACM Transactions on Algorithms 14(4), Article #47 (2018) (originally appeared in SODA 2017)

Combinatorics and Graph Theory

• "A faster algorithm for Vertex Cover parameterized by solution size". With N. Narayanaswamy. STACS 2024

• "Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture". With N. Bansal. Random Structures & Algorithms 62(1), pp. 52-67 (2023)

• "Optimal bounds for the k-cut problem". With A. Gupta, E. Lee, and J. Li.  Journal of the ACM 69(1), Article #2 (2022)

• "Algorithms for weighted independent transversals and strong colouring." With P. Haxell and A. Graf. ACM Transactions on Algorithms 18(1), Article #1 (2021) (Originally appeared in SODA 2021).

• "Bounds and algorithms for graph trusses." With P. Burkhardt and V. Faber. Journal of Graph Algorithms and Applications 24(3), pp. 191-214 (2020)

• "Some results on chromatic number as a function of triangle count". SIAM Journal on Discrete Mathematics 33(1), pp. 546-563 (2019)

• "Edge-coloring linear hypergraphs with medium-sized edges" With V. Faber. Random Structures & Algorithms 55(1), pp. 153-159 (2019)

• "Tight bounds and conjectures for the isolation lemma" With V. Faber. Journal of Combinatorics 9(3), pp. 447-468 (2018)

• “Improved bounds and algorithms for graph cuts and network reliability.” With A. Srinivasan. Random Structures & Algorithms 52(1), pp. 74-135 (2018) (Originally appeared in SODA 2014)

• "A note on near-optimal coloring of shift hypergraphs". With A. Srinivasan. Random Structures & Algorithms 48(1), pp. 53-56 (2016)

• "Distinct volume subsets." With D. Conlon, J. Fox, W. Gasarch, S. Zbarsky. SIAM Journal on Discrete Mathematics 29(1), pp. 472-480 (2015)

• "Sequential importance sampling algorithms for estimating the all-terminal reliability polynomial of sparse graphs." With F. Sullivan. APPROX 2015

• "Fast sequential importance sampling to estimate the graph reliability polynomial.” With F. Sullivan and I. Beichl. Algorithmica 68(4), pp. 916-939 (2012)

Other

• "A new method for estimating species age supports the co-existence of malaria parasites and their mammalian hosts." With J. Silva, A. Egan, C. Arze, J. Spouge. Molecular Biology and Evolution; doi: 10.1093/molbev/msv005 (2015)

• “Critique of the related-key attack concept.” Journal of Coding and Cryptography 59(1-3), pp. 159-168 (2009) (originally appeared in Workshop on Coding and Cryptography 2009)

• “Conserved transposable elements in intergenic regions: recruitment of MIR- and L2-derived sequences in the mouse and human genomes.” With J. Silva, S. Shabalina, J. Spouge, A. Kondrashov. Genetical Research 82(1), pp. 1-18 (2003)