Algorithms and TCS at Dartmouth

News

• (2024-9-5) Multiple graduate student positions available. Consider applying.

Talks & TRG

We have an active student-led "reading group'' where we have active discussions on research in TCS, both internal and external. We often have external speakers, and if you are interested please let any of us know. For Fall 2024, the coordinator is Jonathan Conroy.

Recent Papers & ePrints

• (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.

[more]

Faculty & Research Area

Amit Chakrabarti. Communication Complexity; Information Complexity; Sublinear Algorithms; Approximation Algorithms.

Deeparnab Chakrabarty. Approximation Algorithms; Combinatorial Optimization; Sublinear Algorithms; Algorithmic Game Theory & Economics

Hsien-Chih Chang. Computational Topology & Geometry; Graph Algorithms; Topological Graph Theory; Planarity; Metric Embedding

Prasad Jayanti. Distributed Computing; Concurrent Algorithms; Synchronization & Fault Tolerance

Siddhartha Jayanti. Distributed Computing; Algorithms; Machine Learning; Security, Economics and Computing; Formal Verification

Dan Rockmore. Applied & Computational Harmonic Analysis; FFT; Signal & Image Processing; Computational Biology

Peter Winkler. Randomized Algorithms; Mixing & Markov Chains; Probability & Combinatorics; Statistical Physics

Emerit & Friends

Tom Cormen (Emeritus). Algorithmic Engineering; Parallel computing; CS Education.

Scot Drysdale (Emeritus). Computational Geometry.

Adam Breuer (CS + Govt). Large-scale social network analysis, data summarization, feature selection; behavioral impact of social media, social networks, information/disinformation.

Sergi Elizalde (Math). Enumerative and Additive Combinatorics; Algorithms; Applications of Combinatorics to Comp. Bio. & Dynamical Systems

Raghav Singal (Tuck). Market Analytics; Data-driven Modeling & Optimization; Decision Making

Graduate Students

Reilly Browne. Computational Geometry.

Jonathan Conroy. Metric Embedding; Planar Graph Algorithms; Computational Geometry.

Hang Liao. Graph Query Algorithms; Deep Learning.

Ankita Sarkar. Approximation Algorithms; Clustering.

Recent Alums

Manuel Stoeckl. Communication Complexity, Streaming Algorithms, and Understanding the Interaction of Randomness and Adaptivity. (thesis)

Prantar Ghosh. Graph Algorithms; Data Streaming. (thesis)

Maryam Negahbani. Approximation Algorithms; Combinatorial Optimization; Clustering Algorithms. (thesis)

Anup Joshi. Concurrent Algorithms; Recoverable Shared Memory. (thesis)

Suman K. Bera. Algorithmic Fairness; Scalable Clustering; Communication Complexity; Arithmetic Circuit Complexity.

Sagar Kale. Streaming Algorithms; Matchings; Submodularity; Communication Complexity.