Sampath Kannan

faculty photo

Contact information
Levine 303
Philadelphia, PA 19104
Office: (215) 898-9514
Fax: (215) 898-0587
Education:
Ph.D. (Computer Science)
UC Berkeley, 1990.
Permanent link
 

Description of Research Expertise

Research statement:
Combinatorial algorithms arise in a number of contexts. In computational biology the problems of reconstructing evolutionary trees can be modeled as graph-theoretic optimization problems. Problems related to sequence alignment and pattern matching exploit combinatorial properties of sequences. In compiling various optimization questions such as register allocation can be viewed once again as graph-theoretic problems. A central theme of our research is to design new and efficient algorithms for many of these problems.

Randomness has become central in the design of efficient algorithms and understanding of complexity classes in recent years. Randomization techniques can be used not only to improve the efficiency of algorithms but also to set up a paradigm called program checking to improve the reliability of algorithms. Understanding the power of randomness and utilizing this power in designing efficient algorithms is another important theme of our research.
back to top
Last updated: 08/31/2004
The Trustees of the University of Pennsylvania