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.
Amit Chakrabarti works on complexity theory, with an emphasis on proving lower bounds in concrete computational models, and to a lesser extent on approximation algorithms and space-efficient streaming algorithms. He is a co-inventor of the "information complexity" paradigm. He received an NSF Career Award in 2005.
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 also Chairman of the Department of Mathematics and 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 Albert Bradley Third Century Professor in the Sciences at Dartmouth, and is on the faculties of both computer science and mathematics.