Miscellaneous algorithms
"Improved algorithms for matrix multiplication via sampling and opportunistic matrix multiplication." Algorithmica 86(9), pp. 2822-2844 (2024). (Originally appeared in ESA 2023.)
"Parameter estimation for Gibbs distributions." With V. Kolmogorov. ACM Transactions on Algorithms 21(1), Article #3 (2024) (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. ACM Transactions on Probabilistic Machine Learning 1(1), Article #2 (2024). (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
"A new notion of commutativity for the algorithmic Lovász Local Lemma". With F. Iliopoulos and V. Kolmogorov. Theory of Computing Volume 21 (2025) Article 5 pp. 1-34 (2025). (Originally appeared in RANDOM 2021).
"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)
"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
"Improved parallel derandomization via finite automata with applications" . With J. Giliberti. To appear in ESA
"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)