Sampath Kannan's Home Page

Sampath Kannan

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

Office: Towne 111
To schedule an appointment send email to emilycg at seas dot upenn dot edu

My interests include design and analysis of algorithms, program reliability, and biocomputing.

Selected Publications:

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, Algorithmica, 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)

A Quasi-polynomial Time Algorithm for Sampling Words in a Context-free Language (with V. Gore, M. Jerrum, S. Mahaney, and Z. Sweedyk, To be submitted; see also SODA '95)
Matching Nuts and Bolts (with N. Alon, M. Blum, A. Fiat, M. Naor, and R. Ostrovsky, SODA '94.)
Complexity of Problems on Graphs Represented as OBDDs (with J. Feigenbaum, M.Y. Vardi, and M. Viswanathan)
A bound on the capacity of backoff and acknowledgement-based protocols (with L.A. Goldberg, M. Jerrum, and M. Paterson)
The Relationship between Public Key Encryption and Oblivious Transfer (with Y. Gertner, T. Malkin, O. Reingold, and M. Viswanathan)