Algorithms and Theory


Richard Cole   Ernest Davis   Yevgeniy Dodis  Bud Mishra   Amir Pnueli   Ricky Pollack   Alan Siegel   Joel Spencer   Chee 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, string and pattern matching, and game theory.

Artificial Intelligence (AI) is concerned with the problem of getting computers to perform competently some of the tasks at which human beings excel.  Applied AI-related research is conducted by Natural Language Processing, Vision and Computational Biology groups. In our group, Prof. E. Davis focuses on several theoretical aspects of AI, including representations of commonsense knowledge and spatial and physical reasoning.

We are pleased to announce that Amir Pnueli, 1996 Turing Award winner, joined our group in fall 1999.

Research Interests

Richard Cole Algorithmics, with a current focus on string and pattern matching. Visualization for teaching algorithmics.
Ernest Davis Representations of commonsense knowledge, spatial and physical reasoning; reasoning about knowledge, belief, plans, and goals, and its interaction with physical reasoning.
Yevgeniy Dodis Cryptography and Information Security, (De-)Randomization, ComplexityTheory, Coding theory, Algorithms, Game Theory, Combinatrics.
Bud Mishra Computational biology, including algorithms for identifying DNA associated with cancers, and computational aspects of the optical mapping approach to the Human Genome project. Computational game theory. Robotics. Computational algebra.
Amir Pnueli Automatic proof methods for correctness of programs and hardware designs compositional verification of reactive, real-time, and hybrid systems; temporal logic.
Ricky Pollack Computational geometry: algorithms and mathematical fundamentals. A current focus on algorithms for the topology of semi-algebraic sets, and on geometric transversal theory for families of convex sets.
Alan Siegel Hashing, probabilistic methods, probabilistic inequalities, and geometric inequalities. Computer assisted mathematics education.
Joel Spencer Randomization, probabilistic methods, and random structures.
Chee Yap Geometric-algebraic computation; in particular, developing a robust, easy-to-use library for geometric computation. Visualization and exploitation of foveated images, with applications in GIS visualization and bandwidth limited settings such as the web.

Related Web Pages

Geometry Seminar   Active Visualization   Exact Geometric Computation   Cryptography Group

top | contact