Sampath Kannan

Professor
Department of Computer and Information Science
University of Pennsylvania
Philadelphia, PA 19104
USA

Phone: (215) 898-9514
Fax: (215) 898-0587

Office: Levine 566
I am on leave from the University at NSF until June 30th 2010. I am no longer the Associate Dean of Engineering. The new Associate Dean is Prof. Vijay Kumar in the Mechanical Engineering Department.

c:::ZZZZZZ algorithms, program reliability, and biocomputing.

Selected Publications:

To access some of my recent publications please visit ScholarlyCommons@Penn

Program Checking

Designing Programs that Check Their Work (with M. Blum, JACM V.42 No. 1 pp. 269-291, Jan. 1995; see also STOC 89.)
Checking the Correctness of Memories (with M. Blum, W. Evans, P. Gemmell, and M. Naor, lgorithmica, V.12, No.2/3, 1994, pp. 225-244; see also FOCS 91.)
Program Checkers for Probability Generation (with A. Yao)
Spot-Checkers (with F. Ergun, S. Ravi Kumar, R. Rubinfeld, and M. Viswanathan)
An Approximate L1-Difference Algorithm for Massive Data Streams (with J. Feigenbaum, M. Strauss, and M. Viswanathan)
Testing and Spot-Checking of Data Streams (with J. Feigenbaum, M. Strauss, and M. Viswanathan)

Computational Biology

A Robust Model for Finding Optimal Evolutionary Trees (with M. Farach and T. Warnow, To appear in Algorithmica; see also STOC '93)
A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies (with T. Warnow. SODA 1995.)
Efficient Algorithms For Inverting Evolution (with M. Farach. Manuscript.)
Tight Bounds on the Learnability of Evolution (with A. Ambainis, R. Desper, and M. Farach)
Computing the Local Consensus of Trees (with T. Warnow and S. Yooseph, SODA 1995.)
An Algorithm for Locating Non-Overlapping Regions of Maximum Alignment Score, (with G. Myers, to appear in SIAM J. Computing; see also CPM '93)

Randomness, Cryptography, Complexity