Algorithms and Theory

Faculty

Richard Cole   Yevgeniy Dodis   Subhash Khot   Bud Mishra   Mehryar Mohri   Assaf Naor   Oded Regev   Victor Shoup   Alan R. Siegel   Joel H. Spencer   Chee K. Yap  

Three key issues for an algorithm are: Is it correct? How efficient is it? Can one do better? Our strong and diverse group seeks provable answers to these questions. It focuses on problems and questions in the following areas: computational geometry, computational algebra, randomness (in algorithm design and average case analysis), computational biology, correctness of programs and hardware, and game theory.

Richard Cole has worked on a wide range of algorithmic topics. His current focus is the new area of algorithmic economics. One of the fundamental notions in economics is the concept of equilibrium: for example, prices that approximately balance supply and demand are expected to be the norm. From a computer science perspective, for an equilibrium to be attainable, it has to be computationally feasible to find equilibrium prices and, in addition, the market itself must be able to "compute" such prices. Prof. Cole, his collaborators, and students are studying the computational hardness of the pricing problem and specific pricing algorithms for different market and agent models.

Yevgeniy Dodis is primarily interested in cryptography. His current primary research directions are cryptography based on imperfect randomness, exposure-resilient cryptography, cryptography with biometrics and other noisy data, hash functions and random oracle model and information-theoretic cryptography. Recent achievements include design of special purpose randomness extractors for imperfect sources, formal model of cryptography based on noisy data, design and formalization of intrusion-resilient cryptosystems and new criteria and techniques for design of hash functions.

Subhash Khot is broadly interested in all aspects of algorithms and computational complexity. His specific interests include efficiently computing approximate solutions to NP-hard problems and negative results showing that for many problems, even computing approximate solutions is intractable. His recent works include negative results for semi-definite programming based algorithms, their connection to metric geometry and analysis, and negative results for some learning theory problems.

Bud Mishra has worked in many areas of Computer Science. His current focus is on applications of computer science and mathematical ideas to biological sciences. He has developed optical mapping technology, a successful approach to physical genome mapping. He aims to develop efficient practical algorithmic tools for genome mapping and sequencing. He leads a number of projects in bioinformatics, primarily in genomics and systems biology, including a novel technology aimed at making fast and cheap sequencing of the human genome broadly accessible, a cancer genome atlas, algebraic model checking for systems biology, large-scale models of pandemic flu and smallpox and many others.

Mehryar Mohri's primary research areas are machine learning, theory and algorithms, text and speech processing, and computational biology. This includes in particular the study of the theoretical aspects of machine learning, the design of general and accurate learning algorithms, and their applications to large-scale learning problems such as those found in bioinformatics and language processing.

Oded Regev's research is in mathematical aspects of theoretical computer science.  He is particularly interested in advancing the area of lattice-based cryptography using concepts from quantum computation, analysis, and number theory.

Victor Shoup's research areas are cryptography and computational number theory; he is especially interested in the interactions between these two areas. He designs and analyzes cryptographic primitives and protocols with security properties that can be proven based on clear and reasonable assumptions, and which are nevertheless practical enough to use in the real world. Most recently, he has been working on practical secure deniable protocols (i.e., participants in an exchange using this protocol can deny that it ever took place) based on novel and use of number-theoretic algorithms.

Alan Siegel is interested in the analysis of algorithms and related mathematics, which includes applications from probability, statistics, partial and ordinary differential equations and methods in asymptotic analysis. He works on analysis of probabilistic processes and geometric arrangements of lines. His current research focuses on hashing functions and their properties. He is also interested in K-12 mathematics education and new approaches to teaching algorithms at the college and graduate level.

Joel Spencer is interested in applications of probabilistic methods in discrete mathematics and theoretical computer science. He worked on many topics including Ramsey theory (which studies the conditions under which order must appear in random systems), discrepancy theory (which deals with measuring irregularities of discrete distributions), random graphs and their connections to logic and randomized greedy methods. He is the author of a number of widely known books on probabilistic method.

Chee Yap works in the areas of computational geometry, algebraic computation and visualization. His current research focuses on two themes: exact arithmetic computation and large-scale visualization. Numerical nonrobustness has been called "computer scientists' dirty secret" --everyone knows that our numerical software can break, but we rarely talk about it. The most successful approach to solving the robustness problem in geometry is based on exact geometric computation. Chee Yap and his group are developing techniques for this type of computation based on algebraic zero bounds. Exact geometric computation provides considerable insight into the theory of real computation. The other direction of Chee Yap's work is large-scale visualization, dynamic visualization of geospatial data in particular.

Related Web Pages

Exact geometric computation   Analysis of Computer Systems Group   Geometry seminar   Theory seminar


top | contact webmaster