Recent Papers & ePrints from Dartmouth Algorithms & TCS group

• (2024-10-31) Embedding Planar Graphs into Graphs of Treewidth O(log³ n). Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy, Hung Le, Marcin Pilipczuk, Michał Pilipczuk. SODA 2025.


• (2024-09-19) Learning Partitions using Rank Queries. Deeparnab Chakrabarty, Hang Liao. FSTTCS 2024.


• (2024-09-03) Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing. Deeparnab Chakrabarty, C. Seshadhri. ITCS 2025.


• (2024-03-21) Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams. Amit Chakrabarti, Andrew McGregor, Anthony Wirth. ESA 2024.


• (2024-02-05) Optimal Euclidean Tree Covers. Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than. SoCG 2024.


• (2024-02-05) Computing Diameter+2 in Truly Subquadratic Time for Unit-Disk Graphs. Hsien-Chih Chang, Jie Gao, Hung Le. SoCG 2024.



• (2023-11-13) A Primal-Dual Analysis of Monotone Submodular Maximization. Deeparnab Chakrabarty, Luc Cote.


• (2023-10-11) Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More. Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than. SODA 2024.


• (2023-10-11) Fault-tolerant k-Supplier with Outliers. Deeparnab Chakrabarty, Luc Cote, Ankita Sarkar. STACS 2024.


• (2023-10-5) Finding Missing Items Requires Strong Forms of Randomness. Amit Chakrabarti, Manuel Stoeckl. CCC 2024.


• (2023-9-8) Parallel Submodular Function Minimization. Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, and Aaron Sidford. NeurIPS 2023 (Spotlight).


• (2023-9-5) From Curves to Words and Back Again: Geometric Computation of Minimum-Area Homotopy. Hsien-Chih Chang, Brittany Terese Fasy, Bradley McCoy, David L. Millman, Carola Wenk. WADS 2023.


• (2023-6-16) Learning Spanning Forests Optimally using CUT Queries in Weighted Undirected Graphs. Hang Liao, Deeparnab Chakrabarty. ALT 2023.


• (2023-6-13) Covering Planar Metrics (and Beyond): O(1) Trees Suffice. Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than. FOCS 2023.


• (2023-5-31) Low-Memory Algorithms for Online and W-Streaming Edge Coloring. Prantar Ghosh, Manuel Stoeckl.


• (2023-4-3) A d^1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids Hadley Black, Deeparnab Chakrabarty, C. Seshadhri. FOCS 2023.


• (2023-2-1) Constant RMR Recoverable Mutex under System-wide Crashes. Prasad Jayanti, Siddhartha Jayanti, Anup Joshi. SPAA 2023.


• (2023-2-1) A Universal Technique for Machine-Certified Proofs of Linearizable Algorithms. Prasad Jayanti, Siddhartha Jayanti, Ugur Y. Yavuz, Lizzie Hernandez. POPL 2024.


• (2023-1-31) Durable Algorithms for Writable LL/SC and CAS with Dynamic Joining. Prasad Jayanti, Siddhartha Jayanti, Sucharita Jayanti. PODC 2023



• (2022-12-20) Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms. Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl. PODS 2023.


• (2022-11-10) Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester. Hadley Black, Deeparnab Chakrabarty, C. Seshadhri. STOC 2023.


• (2022-11-9) Streaming algorithms for the missing item finding problem. Manuel Stoeckl. SODA 2023.


• (2022-7-9) Improved Lower Bounds for Submodular Function Minimization. Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford. FOCS 2022.


• (2022-6-30) Approximation Algorithms for Continuous Clustering and Facility Location Problems. Deeparnab Chakrabarty, Maryam Negahbani, Ankita Sarkar. ESA 2022.


• (2022-6-21) Near-Linear ε-Emulators for Planar Graphs. Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan. STOC 2022.


• (2022-6-9) Improved Approximation for Fair Correlation Clustering. Sara Ahmadian, Maryam Negahbani. AISTATS 2023.


• (2022-4-17) A New Dynamic Algorithm for Densest Subhypergraphs. Suman K. Bera, Sayan Bhattacharya, Jayesh Choudhari, Prantar Ghosh. WWW 2022.


• (2022-4-8) Deterministic, Near-Linear ε-Approximation Algorithm for Geometric Bipartite Matching. Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra, Allen Xiao. STOC 2022.



• (2021-12-21) Counting Simplices in Hypergraph Streams. Amit Chakrabarti, Themistoklis Haris. ESA 2022.


• (2021-11-14) A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection. Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna. FOCS 2021, SICOMP.


• (2021-9-23) Adversarially Robust Coloring for Graph Streams. Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl. ITCS 2022.


• (2021-7-13) The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries. Amit Chakrabarti, Manuel Stoeckl.


• (2021-6-23) Better Algorithms for Individually Fair k-Clustering. Deeparnab Chakrabarty, Maryam Negahbani. NeurIPS 2021.


• (2021-5-18) Vertex Ordering Problems in Directed Graph Streams. Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova. SODA 2020.


• (2021-5-18) Revisiting Priority k-Center: Fairness and Outliers. Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, Maryam Negahbani. ICALP 2021.


• (2021-2-23) Robust k-Center with Two Types of Radii. Deeparnab Chakrabarty, Maryam Negahbani. IPCO 2021, Math. Programming.