This project pursues research in two main arenas.
1. Randomized algorithms for important problem domains. These include
1. Geometric pattern matching 2. Finding optimal clusterings of data points with respect to a simple quadratic-penalty cost function. 3. Statistical inference of high of dimensional mixture models, as a formulation of hard clustering problems. Potential applications include analysis of behavior modes of large dynamical systems. 4. Property testing.
Highly efficient algorithms for geometric pattern matching will be useful for searching in compressed images, as well as in geometric models produced in CAD/CAM systems. Good clustering algorithms will be applied when large columns of data need to be analyzed and categorized, as is the case in disciplines including Statistics. Demographics, Economics, Agriculture, Psychology, Machine Vision. Biology (both for taxonomy and for protein classification), and citation pattern analysis (for the scientific literature or the hyperlink structure of the world wide web).
2. Quantum computation. Problems pursued are
1. Feasibility of large-scale quantum computation. Existing designs for quantum computers provide small systems with carefully controllable Hamiltonians, but these do not scale to devices with enough degrees of freedom to carry out interesting computations. Research will be conducted in order to surmount this obstacle.
2. Quantum algorithms. Certain problems, including factorization, can be solved on a quantum computer exponentially more rapidly than in the best known classical methods. Work is pursued exploring the capabilities of quantum algorithms.
3. Quantum cryptographic primitives. The flip side of the computational power of quantum computers is their ability to defeat the current leading crytographic methods. Work is pursued on devising candidates for quantum one-way functions and other cryptographic primitives.
The educational component includes
An emphasis on open-ended assignments calling for student creativity.
Extension of the algorithms curriculum to cover important methods in coding and data compression.
Narrowing the curricular divide between theory and practice.
Use of new technologies in the classroom.
Initiation of undergraduate research.
