Algorithms and Theory
Faculty
Richard Cole
Ernest Davis
Yevgeniy Dodis
Bud Mishra
Amir Pnueli
Ricky Pollack
Alan Siegel
Joel Spencer
Chee Yap
Description
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 AIrelated 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,
realtime, and hybrid systems; temporal logic.

Ricky Pollack

Computational geometry: algorithms and mathematical
fundamentals. A current focus on algorithms for the topology of
semialgebraic 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

Geometricalgebraic computation; in particular, developing a robust,
easytouse 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 webmaster@cs.nyu.edu
