SAMPATH KANNAN

PUBLICATIONS


2014
 
Optimal Provision-After-Wait in Healthcare  
Braverman,M., Chen,J., and Kannan,S.  
ITCS 2014  
   
2013  
"On the complexity of shortest path problems on discounted cost graphs"
Alur, R., Kannan, S., Tian, K., Yuan, Y.
Lecture Notes in Computer Science
 
   

"Finding Optimal 1-Endpoint-Crossing Trees"

 
Pitler, E., Kannan, S. and Marcus, M.  
Transactions of the Association for Computational Linguistics (TACL) Volume 1 (2013)  
   
"AS-CRED: Reputation and alert service for interdomain routing"
Chang, J., Venkatasubramanian, K.K., West, A.G., Kannan, S., Lee, I., Loo, B.T., Sokolsky, O.
IEEE Systems Journal
 
   
2012  
"The exponential mechanism for social welfare: Private, truthful, and nearly optimal"

Huang, Z., Kannan, S.

Annual IEEE Symposium on Foundations of Computer Science
 
 
"Dynamic Programming for Higher Order Parsing of Gap-Minding Trees"  
Pitler, E., Kannan, S., and Marcus, M.  
EMNLP 2012.  
   
"Improved hardness results for profit maximization pricing problems with unlimited supply"
Chalermsook, P., Chuzhoy, J., Kannan, S., Khanna, S.
Lecture Notes in Computer Science
 
   
2011  
"Algorithms for the generalized sorting problem"
Huang, Z., Kannan, S., Khanna, S.
Annual IEEE Symposium on Foundations of Computer Science
 
   
"ToMaTo: A trustworthy code mashup development tool"
Chang, J., Venkatasubramanian, K., West, A.G., Kannan, S., Sokolsky, O., Kim, M.J., Lee, I.
ACM International Conference Proceeding Series
 
   
"Algorithms for the generalized sorting problem"
Huang, Zhiyi ; Kannan, Sampath ; Khanna, Sanjeev
IEEE 52nd Annual Symposium on Foundations of Computer Science
 
   
"On sampling from multivariate distributions"
Huang, Z., Kannan, S.
Lecture Notes in Computer Science
 
   
"AS-TRUST: A trust quantification scheme for autonomous systems in BGP"
Chang, J., Venkatasubramanian, K.K., West, A.G., Kannan, S., Loo, B.T., Sokolsky, O., Lee, I.
Lecture Notes in Computer Science
 
   
2010  
"Spatio-temporal analysis of wikipedia metadata and the STiki anti-vandalism tool"
West, A.G., Kannan, S., Lee, I.
Proceedings of WikiSym 2010 - The 6th International Symposium on Wikis and Open Collaboration
 
   
"STiki: An anti-vandalism tool for wikipedia using spatio-temporal analysis of revision metadata"
West, A.G., Kannan, S., Lee, I.
Proceedings of WikiSym 2010 - The 6th International Symposium on Wikis and Open Collaboration
 
   
"Detecting Wikipedia vandalism via spatio-temporal analysis of revision metadata?"
West, A.G., Kannan, S., Lee, I.
Proceedings of the 3rd European Workshop on System Security
 
   
2009  
"Reconstructing numbers from pairwise function values"
Chen, S., Huang, Z., Kannan, S.
Lecture Notes in Computer Science
 
   
"Reconstructing numbers from pairwise function values"
Chen, Shiteng ; Huang, Zhiyi ; Kannan, Sampath
Algorithms and computation
 
   
"QuanTM: A Quantitative Trust Management system"
West, A.G., Aviv, A.J., Chang, J., Prabhu, V.S., Blaze, M., Kannan, S., Lee, I., Smith, J.M., Sokolsky, O.
Proceedings of the 2nd European Workshop on System Security
 
   
"Dynamic trust management"
Blaze, M., Kannan, S., Lee, I., Sokolsky, O., Smith, J.M., Keromytis, A.D., Lee, W.
Computer
 
   
2008  
"Graph distances in the data-stream model"
Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.
SIAM Journal on Computing
 
   
"STCON in directed unique-path graphs"
Kannan, S., Khanna, S., Roy, S.
Leibniz International Proceedings in Informatics
 
   
"Graph Distances in the Data-Stream Model"
Feigenbaum, Joan ; Kannan, Sampath ; McGregor, Andrew ; Suri, Siddharth ; Zhang, Jian
SIAM J. Comput.
 
   
2007  
"Checking and spot-checking the correctness of priority queues"
Chu, M., Kannan, S., McGregor, A.
Lecture Notes in Computer Science
 
   
"Efficient Enumeration of Phylogenetically Informative Substrings"
Angelov, Stanislav ; Harb, Boulos ; Kannan, Sampath ; Khanna, Sanjeev ; Kim, Junhyong
J. Comput. Biol.
 
   
"Efficient enumeration of phylogenetically informative substrings"
Angelov, S., Harb, B., Kannan, S., Khanna, S., Kim, J.
Journal of Computational Biology
 
   
2006  
"Randomized pursuit-evasion with local visibility"
Isler, V., Kannan, S., Khanna, S.
SIAM Journal on Discrete Mathematics
 
   
"Efficient enumeration of phylogenetically informative substrings"
Angelov, S., Harb, B., Kannan, S., Khanna, S., Kim, J.
Lecture Notes in Computer Science
 
   
"Simulation-based graph similarity"
Sokolsky, O., Kannan, S., Lee, I.
Lecture Notes in Computer Science
 
   
"Randomized pursuit-evasion with local visibility"
Isler, Volkan ; Kannan, Sampath ; Khanna, Sanjeev
SIAM Journal on Discrete Mathematics
 
   
"Efficient Enumeration of Phylogenetically Informative Substrings"
Angelov, Stanislav ; Harb, Boulos ; Kannan, Sampath ; Khanna, Sanjeev ; Kim, Junhyong
Lecture Notes in Computer Science
 
   
"Steering of Discrete Event Systems: Control Theory Approach"
Easwaran, A., Kannan, S., Sokolsky, O.
Electronic Notes in Theoretical Computer Science
 
   
"Weighted isotonic regression under the L 1 norm"
Angelov, S., Harb, B., Kannan, S., Wang, L.-S.
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
 
   
2005  
"On graph problems in a semi-streaming model"
Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.
Theoretical Computer Science
 
   
"Locating and capturing an Evader in a polygonal environment"
Isler, V., Kannan, S., Khanna, S.
Springer Tracts in Advanced Robotics
 
   
"More on reconstructing strings from random traces: Insertions and deletions"
Kannan, S., McGregor, A.
IEEE International Symposium on Information Theory
 
   
"Approximating the best-fit tree under Lp norms"
Harb, B., Kannan, S., McGregor, A.
Approximation, randomization and combinatorial optimization
 
   
"Randomized pursuit-evasion in a polygonal environment"
Isler, V., Kannan, S., Khanna, S.
IEEE Transactions on Robotics
 
   
"Computing diameter in the streaming and sliding-window models"
Feigenbaum, Joan ; Kannan, Sampath ; Zhang, Jian
Algorithmica
 
   
"Better alternatives to OSPF routing"
Fong, J.H., Gilbert, A.C., Kannan, S., Strauss, M.J.
Algorithmica (New York)
 
   
"Graph distances in the streaming model: The value of space"
Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.
Annual ACM-SIAM Symposium on Discrete Algorithms
 
   
2004  
"Inferring mixtures of Markov chains"
Batu, T., Guha, S., Kannan, S.
Lecture Notes in Artificial Intelligence
 
   
"Randomized pursuit-evasion with limited visibility"
Isler, Volkan ; Kannan, Sampath ; Khanna, Sanjeev
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
 
   
"Reconstructing strings from random traces"
Batu, Tuǧkan ; Kannan, Sampath ; Khanna, Sanjeev ; McGregor, Andrew
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
 
   
"Guest editors' foreword"
Kannan, Sampath ; Yannakakis, Mihalis
J. Comput. System Sci.
 
   
"Genome identification and classification by short oligo arrays"
Angelov, S., Harb, B., Kannan, S., Khanna, S., Kim, J., Wang, L.-S.
Lecture Notes in Computer Science
 
   
"On graph problems in a semi-streaming model"
Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.
Lecture Notes in Computer Science
 
   
"Sampling based sensor-network deployment"
Isler, V., Kannan, S., Daniilidis, K.
IEEE/RSJ International Conference on Intelligent Robots and Systems
 
   
"Computing diameter in the streaming and sliding-window models"
Feigenbaum, J., Kannan, S., Zhang, J.
Algorithmica (New York)
 
   
"Polyhedral flows in hybrid automata"
Alur, R., Kannan, S., La Torre, S.
Formal Methods in System Design
 
   
"VC-dimension of exterior visibility"
Isler, V., Kannan, S., Daniilidis, K., Valtr, P.
IEEE Transactions on Pattern Analysis and Machine Intelligence
 
   
"Randomized Pursuit-Evasion with Limited Visibility"
Isler, V., Kannan, S., Khanna, S.
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
 
   
"Reconstructing Strings from Random Traces"
Batu, T., Kannan, S., Khanna, S., McGregor, A.
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
 
   
"Java-MaC: A Run-Time Assurance Approach for Java Programs"
Kim, M., Viswanathan, M., Kannan, S., Lee, I., Sokolsky, O.
Formal Methods in System Design
 
   
"A bound on the capacity of backoff and acknowledgment-based protocols"
Goldberg, L.A., Jerrum, M., Kannan, S., Paterson, M.
SIAM Journal on Computing
 
   
2003  
"Local exploration: Online algorithms and a probabilistic framework"
Isler, V., Kannan, S., Daniilidis, K.
IEEE International Conference on Robotics and Automation
 
   
"An approximate L1-difference algorithm for massive data streams"
Feigenbaum, J., Kannan, S., Strauss, M.J., Viswanathan, M.
SIAM Journal on Computing
 
   
"Selection with monotone comparison costs"
Kannan, S., Khanna, S.
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
 
   
2002  
"Computational analysis of run-time monitoring: Fundamentals of java-MaC"
Kim, M., Kannan, S., Lee, I., Sokolsky, O., Viswanathan, M.
Electronic Notes in Theoretical Computer Science
 
   
"Testing and spot-checking of data streams"
Feigenbaum, J., Kannan, S., Strauss, M., Viswanathan, M.
Algorithmica (New York)
 
   
"Thresholds and optimal binary comparison search trees"
Anderson, R., Kannan, S., Karloff, H., Ladner, R.E.
Journal of Algorithms
 
   
2001  
"Thresholds and optimal binary comparison search trees"
Anderson, Richard ; Kannan, Sampath ; Karloff, Howard ; Ladner, Richard E.
Foundations of software technology and theoretical computer science
 
   
"Java-MaC: A run-time assurance tool for Java programs"
Kim, M., Kannan, S., Lee, I., Sokolsky, O., Viswanathan, M.
Electronic Notes in Theoretical Computer Science
 
   
2000  
"Relationship between public key encryption and oblivious transfer"
Gertner, Yael, Kannan, Sampath, Malkin, Tal, Reingold, Omer, Viswanathan, Mahesh
Annual Symposium on Foundations of Computer Science - Proceedings
 
   
"Spot-checkers"
Ergün, F., Kannan, S., Kumar, S.R., Rubinfeld, R., Viswanathan, M.
Journal of Computer and System Sciences
 
   
"Steering of real-time systems based on monitoring and checking"
Sokolsky, Oleg, Kannan, Sampath, Kim, Moonjoo, Lee, Insup, Viswanathan, Mahesh
Proceedings of the Workshop on Object-Oriented Real-Time Dependable Systems (WORDS)
 
   
"The Relationship between Public Key Encryption and Oblivious Transfer"
Gertner, Yael ; Kannan, Sampath ; Malkin, Tal ; Reingold, Omer ; Viswanathan, Mahesh
41st Annual Symposium on Foundations of Computer Science
 
   
"A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols"
Goldberg, Leslie Ann ; Jerrum, Mark ; Kannan, Sampath ; Paterson, Mike
Automata, languages and programming
 
   
"Testing and spot-checking of data streams"
Feigenbaum, J., Kannan, S., Strauss, M., Viswanathan, M.
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
 
   
1999  
"Approximate L1-difference algorithm for massive data streams"
Feigenbaum, J., Kannan, S., Strauss, M., Viswanathan, M.
Annual Symposium on Foundations of Computer Science
 
   
"An approximate L1-difference algorithm for massive data streams" (extended abstract)
Feigenbaum, J. ; Kannan, S. ; Strauss, M. ; Viswanathan, M.
40th Annual Symposium on Foundations of Computer Science
 
   
"Complexity of problems on graphs represented as OBDDs"
Feigenbaum, Joan ; Kannan, Sampath ; Vardi, Moshe Y. ; Viswanathan, Mahesh
Chicago J. Theoret. Comput. Sci.
 
   
"Communicating hierarchical state machines"
Alur, Rajeev ; Kannan, Sampath ; Yannakakis, Mihalis
Automata, languages and programming
 
   
"Efficient algorithms for inverting evolution"
Farach, M., Kannan, S.
Journal of the ACM
 
   
"Formally specified monitoring of temporal properties"
Kim, M., Viswanathan, M., Ben-Abdallah, H., Kannan, S., Lee, I., Sokolsky, O.
Euromicro Conference on Real-Time Systems
 
   
1998  
"A formal framework for evaluating heuristic programs"
Cowen, Lenore ; Feigenbaum, Joan ; Kannan, Sampath
Ann. Math. Artificial Intelligence
 
   
"Complexity of problems on graphs represented as OBDDs" (extended abstract)
Feigenbaum, J., Kannan, S., Vardi, M.Y., Viswanathan, M.
Lecture Notes in Computer Science
 
   
"Computing the local consensus of trees"
Kannan, S., Warnow, T., Yooseph, S.
SIAM Journal on Computing
 
   
"On the complexity and approximation of syntenic distance"
DasGupta, B., Jiang, T., Kannan, S., Li, M., Sweedyk, E.
Discrete Applied Mathematics
 
   
"Register Allocation in Structured Programs"
Kannan, S., Proebsting, T.
Journal of Algorithms
 
   
"Spot-checkers"
Ergun, Funda, Kannan, Sampath, Kumar, S.Ravi, Rubinfeld, Ronitt, Viswanathan, Mahesh
Conference Proceedings of the Annual ACM Symposium on Theory of Computing
 
   
1997  
"A fast algorithm for the computation and enumeration of perfect phylogenies"
Kannan, S., Warnow, T.
SIAM Journal on Computing
 
   
"Consensus of trees - Desirable properties and computational methods"
Kannan, S., Sweedyk, Z.
Journal of the Indian Institute of Science
 
   
"Group testing problems with sequences in experimental molecular biology"
Farach, M., Kannan, S., Knill, E., Muthukrishnan, S.
Proceedings of the International Conference on Compression and Complexity of Sequences
 
   
"Nearly tight bounds on the learnability of evolution"
Ambainis, Andris, Desper, Richard, Farach, Martin, Kannan, Sampath
Annual Symposium on Foundations of Computer Science
 
   
"A Quasi-polynomial-time Algorithm for Sampling Words from a Context-Free Language"
Gore, V., Jerrum, M., Kannan, S., Sweedyk, Z., Mahaney, S.
Information and Computation
 
   
"On the complexity and approximation of syntenic distance"
DasGupta, B., Jiang, T., Kannan, S., Li, M., Sweedyk, Z.
Proceedings of thr Annual International Conference on Computational Molecular Biology
 
   
1996  
"Determining the Evolutionary Tree Using Experiments"
Kannan, S.K., Lawler, E.L., Warnow, T.
Journal of Algorithms
 
   
"An algorithm for locating nonoverlapping regions of maximum alignment score"
Kannan, S.K., Myers, E.W.
SIAM Journal on Computing
 
   
"Oracles and queries that are sufficient for exact learning"
Bshouty, N.H., Cleve, R., Gavaldà, R., Kannan, S., Tamon, C.
Journal of Computer and System Sciences
 
   
"A formal framework for evaluating heuristic programs"
Cowen, Lenore ; Feigenbaum, Joan ; Kannan, Sampath
Automata, languages and programming
 
   
"Efficient algorithms for inverting evolution"
Farach, Martin, Kannan, Sampath
Conference Proceedings of the Annual ACM Symposium on Theory of Computing
 
   
1995  
"Hen's teeth and whale's feet: generalized characters and their compatibility"
Benham, C., Kannan, S., Paterson, M., Warnow, T.
Journal of computational biology : a journal of computational molecular cell biology
 
   
"Of Chicken Teeth and Mouse Eyes, or Generalized Character Compatibility"
Benham, Craig ; Kannan, Sampath ; Warnow, Tandy
Combinatorial pattern matching
 
   
"Tree reconstruction from partial orders"
Kannan, Sampath K., Warnow, Tandy J.
SIAM Journal on Computing
 
   
"A robust model for finding optimal evolutionary trees"
Farach, M., Kannan, S., Warnow, T.
Algorithmica
 
   
"Designing programs that check their work"
Blum, Manuel, Kannan, Sampath
Journal of the ACM
 
   
"Minimizing space usage in evaluation of expression trees"
Biswas, Sandip K. ; Kannan, Sampath
Foundations of software technology and theoretical computer science
 
   
"A fast algorithm for the computation and enumeration of perfect phylogenies when the number of character states is fixed"
Kannan, Sampath ; Warnow, Tandy
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms
 
   
"Counting and random generation of strings in regular Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms"
Kannan, Sampath ; Sweedyk, Z. ; Mahaney, Steve
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms
 
   
"Computing the local consensus of trees"
Kannan, Sampath ; Warnow, Tandy; Yooseph, Shibu
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms
 
   
1994  
   
"Checking the correctness of memories"
Blum, M., Evans, W., Gemmell, P., Kannan, S., Naor, M.
Algorithmica
 
   
"Inferring evolutionary history from DNA sequences"
Kannan, Sampath K., Warnow, Tandy J.
SIAM Journal on Computing
 
   
"Call forwarding: a simple interprocedural optimization technique for dynamically typed languages"
De Bosschere, Koen, Debray, Saumya, Gudeman, David, Kannan, Sampath
Conference Record of the Annual ACM Symposium on Principles of Programming Languages
 
   
"Matching nuts and bolts"
Alon, Noga, Blum, Manuel, Fiat, Amos, Kannan, Sampath, Naor, Moni, Ostrovsky, Rafail
Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
 
   
1993  
"On the query complexity of learning"
Kannan, Sampath K.
Proceedings of the 6th Annual ACM Conference on Computational Learning Theory
 
   
"Robust model for finding optimal evolutionary trees"
Farach, Martin, Kannan, Sampath, Warnow, Tandy
Conference Proceedings of the Annual ACM Symposium on Theory of Computing
 
   
"Tree reconstruction from partial orders. Algorithms and data structures"
Kannan, Sampath ; Warnow, Tandy
Algorithms and data structures
 
   
"An algorithm for locating nonoverlapping regions of maximum alignment score"
Kannan, Sampath K. ; Myers, Eugene W.
Combinatorial pattern matching
 
   
"Two probabilistic results on merging"
Fernandez de la Vega, Wenceslas ; Kannan, Sampath ; Sántha, Miklós
SIAM J. Comput.
 
   
1992  
"Tiling polygons with parallelograms"
Kannan, S., Soroker, D.
Discrete & Computational Geometry
 
   
"Implicit representation of graphs"
Kannan, Sampath ; Naor, Moni ; Rudich, Steven
SIAM J. Discrete Math.
 
   
"Triangulating 3-colored graphs"
Kannan, Sampath K. ; Warnow, Tandy J.
SIAM J. Discrete Math.
 
   
1991  
"Program checkers for probability generation"
Kannan, Sampath ; Yao, Andrew
Automata, languages and programming. Lecture Notes in Comput. Sci.
 
   
"Triangulating three-colored graphs"
Kannan, Sampath K. ; Warnow, Tandy J.
Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms
 
   
"Checking the correctness of memories"
Blum, Manuel, Evans, Will, Gemmell, Peter, Kannan, Sampath, Naor, Moni
Annual Symposium on Foundations of Computer Science
 
   
"Inferring evolutionary history from DNA sequences"
Kannan, Sampath, Warnow, Tandy
IEEE Transactions on Industry Applications
 
   
1990  
"Lower bounds on random-self-reducibility"
Feigenbaum, Joan, Kannan, Sampath, Nisan, Noam
Fifth Annual Structure in Complexity Theory Conference. IEEE Comput. Soc. Press
 
   
"Two probabilistic results on merging"
Fernandez de la Vega, Wenceslao ; Kannan, Sampath ; Sántha, Miklós
Algorithms. Lecture Notes in Comput. Sci.
 
   
1989  
"Designing programs that check their work"
Blum, Manuel, Kannan, Sampath
Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing
 
   
1988  
"The generation of random permutations on the fly"
Brassard, G., Kannan, S.
Information Processing Letters
 
   
1985  
"A framework for the study of cryptographic protocols"
Berger, Richard ; Kannan, Sampath ; Peralta, René
Advances in cryptology—CRYPTO '85. Lecture Notes in Comput. Sci.