Algorithms and TCS at Dartmouth

News

• (2023-8-24) Faculty position in Algorithms. (Interfolio page)
• (2023-8-15) 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 Spring 2024, the coordinator is Jonathan Conroy.

Recent Papers & ePrints

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


• (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) When a random tape is not enough: lower bounds for a problem in adversarially robust streaming. Amit Chakrabarti, Manuel Stoeckl.


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

[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

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

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

Hang Liao. Graph Query Algorithms; Deep Learning.

Ankita Sarkar. Approximation Algorithms; Clustering .

Manuel Stoeckl. Communication Complexity, Streaming Algorithms, and Understanding the interaction of Randomness and Adaptivity.

Recent Alums

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.