Sampath Kannan

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

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

• 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)

Algorithms for Computer Systems

• Register Allocation in Structured Programs (with T. Proebsting, Submitted to J. of Algorithms; see also SODA '95).

  ---