2025
"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. (Originally appeared in RANDOM 2021).
"Improved parallel derandomization via finite automata with applications" . With J. Giliberti. To appear in ESA
2024
"Parameter estimation for Gibbs distributions." With V. Kolmogorov. ACM Transactions on Algorithms 21(1), Article #3 (2024) (Originally appeared in ICALP 2023)
"Improved algorithms for matrix multiplication via sampling and opportunistic matrix multiplication." Algorithmica 86(9), pp. 2822-2844. (Originally appeared in ESA 2023)
"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. (Originally appeared in APPROX 2021)
"A faster algorithm for Vertex Cover parameterized by solution size". With N. Narayanaswamy. STACS
2023
"Exponentially faster massively parallel maximal matching." With S. Behnezhad and M. Hajiaghayi. Journal of the ACM 70(5), Article #34 (Originally appeared in FOCS 2019)
"Deterministic algorithms for the Lovasz Local Lemma: simpler, more general, and more parallel". Random Structures & Algorithms 63(3), pp. 716-752 (Originally appeared in SODA 2022)
"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 (Originally appeared in PODC 2021).
"Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture". With N. Bansal. Random Structures & Algorithms 62(1), pp. 52-67
2022
"Comparison of two convergence criteria for the variable-assignment Lopsided Lovasz Local Lemma". Electronic Journal of Combinatorics 29(4), #P4.10 (2022)
"Optimal bounds for the k-cut problem". With A. Gupta, E. Lee, and J. Li. Journal of the ACM 69(1), Article #2
"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.)
2021
"Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma". ACM Transactions on Algorithms 17(1), Article #1 (Originally appeared in SODA 2019)
"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).
"Partial resampling to approximate covering integer programs." With A. Chen and A. Srinivasan. Random Structures & Algorithms 58(1), pp. 68-93 (Originally appeared in SODA 2016)
2020
"New bounds for the Moser-Tardos distribution." Random Structures & Algorithms 57(1), pp. 97-131
"Distributed local approximation algorithms for maximum matching in graphs and hypergraphs". SIAM Journal on Computing 49(4), pp. 711-746 (originally appeared in FOCS 2019)
"Bounds and algorithms for graph trusses." With P. Burkhardt and V. Faber. Journal of Graph Algorithms and Applications 24(3), pp. 191-214.
2019
“The Moser-Tardos framework with partial resampling.” With A. Srinivasan. Journal of the ACM 66(5), Article #36 (Extended version of paper from FOCS 2013)
"Approximation algorithms for stochastic clustering". With S. Li, T. Pensyl, A. Srinivasan, K. Trinh. Journal of Machine Learning Research 20(153), pp. 1-33 (originally appeared in NeurIPS 2018). (NOTE: the version published on JMLR has an error. The arxiv version, linked here, is correct)
"Derandomized concentration bounds for polynomials, and hypergraph maximal independent set". ACM Transactions on Algorithms 15(3), Article #43 (originally appeared in SODA 2018)
"Deterministic parallel algorithms for bilinear objective functions". Algorithmica 81(3), pp. 1288-1318
"Some results on chromatic number as a function of triangle count". SIAM Journal on Discrete Mathematics 33(1), pp. 546-563
"Edge-coloring linear hypergraphs with medium-sized edges" With V. Faber. Random Structures & Algorithms 55(1), pp. 153-159
"A lottery model for center-type problems with outliers." With T. Pensyl, A. Srinivasan, K. Trinh. ACM Transactions on Algorithms 15(3), Article #36 (originally appeared in APPROX 2017)
2018
"On derandomizing local distributed algorithms" With F. Kuhn and M. Ghaffari. FOCS
"Distributed (Δ+1)-coloring in sublogarithmic rounds" With J. Schneider and H. Su. Journal of the ACM 65(4), Article #19 (Originally appeared in STOC 2016)
"Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovász Local Lemma" ACM Transactions on Algorithms 14(4), Article #47 (originally appeared in SODA 2017)
"Tight bounds and conjectures for the isolation lemma" With V. Faber. Journal of Combinatorics 9(3), pp. 447-468.
“Improved bounds and algorithms for graph cuts and network reliability.” With A. Srinivasan. Random Structures & Algorithms 52(1), pp. 74-135. (Originally appeared in SODA 2014)
2017
"A constructive Lovász Local Lemma for permutations" With A. Srinivasan. Theory of Computing 13(17), pp. 1-41 (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 (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 (Originally appeared in SODA 2017)
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
"Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovász Local Lemma" ACM Transactions on Algorithms 13(1), Article #17 (Originally appeared in SODA 2015)
“Efficient computation of sparse structures” With E. Morsy, G. Pandurangan, P. Robinson, A. Srinivasan. Random Structures & Algorithms 49(2), pp. 322-344 (Originally appeared in ICALP 2013)
"A note on near-optimal coloring of shift hypergraphs". With A. Srinivasan. Random Structures & Algorithms 48(1), pp. 53-56
2015
"Algorithms and Generalizations for the Lovász Local Lemma" Doctoral Thesis.
"Distinct volume subsets." With D. Conlon, J. Fox, W. Gasarch, S. Zbarsky. SIAM Journal on Discrete Mathematics 29(1), pp. 472-480.
"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
"Sequential importance sampling algorithms for estimating the all-terminal reliability polynomial of sparse graphs." With F. Sullivan. APPROX.
2014 and earlier
“Constraint satisfaction, packet routing, and the Lovász Local Lemma”. With A. Srinivasan. STOC 2013
"Fast sequential importance sampling to estimate the graph reliability polynomial.” With F. Sullivan and I. Beichl. Algorithmica 68(4), pp. 916-939 (2012)
"Linear algebra and sequential importance sampling for network reliability.” With F. Sullivan and I. Beichl. Winter Simulation Conference 2011
“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)