Theory and Algorithms

The theory of computing is the study of efficient computation, models of computational processes, and their limits. It has emerged over the past few decades as a deep and fundamental scientific discipline. Many fundamental questions are still unanswered. This field has potential to substantially impact current issues in the development of systems and software, the nation's network and communications infrastructure, and the physical and biological sciences.

Our faculty and students are actively involved in areas such as the design of fundamental algorithms, combinatorial optimization, distributed and parallel computation, machine learning, computational complexity theory, computational geometry and topology, dynamical systems, multimedia and image processing, compression, and the computational sciences.

Reading Group

Dartmouth has an active Theory Reading Group (TRG). We have vigorous, exciting discussions and presentations on recent research in theoretical computer science (TCS). Everyone is welcome. Please consult the TRG web page for more details.

Faculty

Amit Chakrabarti works on complexity theory, with an emphasis on proving lower bounds in concrete computational models; on sublinear algorithms, especially for streaming and "big" data; and to a lesser extent on approximation algorithms for combinatorial optimization. He is a co-inventor of the "information complexity" paradigm. He received an NSF CAREER Award in 2005 and a Wolfson Award in 2016.

Deeparnab Chakrabarty works broadly in designing algorithms for optimization problems. His area of expertise is in approximation algorithms for scheduling, clustering, and network design problems. He also works on sublinear algorithms, property testing, and submodular function optimization. He has also dabbled with algorithmic problems arising in game theory and economics.

Tom Cormen works on algorithm engineering and parallel computing. He focuses on algorithms and software infrastructure to mitigate the high latency inherent in accessing the outer levels of the memory hierarchy and in interprocessor communication. He is coauthor of the leading textbook on computer algorithms, Introduction to Algorithms.

Scot Drysdale works in computational geometry. Much of his work has been on Voronoi diagrams for various shapes and distance measures, on Delaunay triangulations, and on applications of these structures. He has also worked on problems arising from numerically controlled machining.

Lisa Fleischer works on algorithm design and analysis for problems in network routing and design, combinatorial optimization, and linear programming. Her recent work focusses in the area of algorithmic economics and game theory. She received the Fulkerson Prize in 2003, an NSF CAREER Award in 2000.

Prasad Jayanti works on concurrent/distributed algorithms and lower bounds, especially for problems relating to synchronization and fault tolerance in asynchronous systems. His recent work includes snapshot algorithms, abortable locks, and priority locks. He received the Alfred P. Sloan Research Fellowship in 2000.

Dan Rockmore works mainly in applied and computational harmonic analysis, primarily related to generalizations of the fast Fourier transform. He has worked in signal and image processing and computational biology. He is the Associate Dean for the Sciences and serves on the external faculty of the Santa Fe Institute where he is Director of the Complex Systems Summer School.

Peter Winkler devises and studies algorithms, for example those which rely on rapidly mixing Markov chains. His methods usually involve combinatorics, probability or statistical physics. Formerly Director of Fundamental Mathematics Research at Bell Labs, he is now William Morrill Professor of Mathematics and Computer Science at Dartmouth.