An Evaluation Framework for Reputation Management Systems (2009)
West, Andrew G, Kannan, Sampath, Lee, Insup, Sokolsky, Oleg
Reputation management (RM) is employed in distributed and peer-to-peer networks to help users compute a measure of trust in other users based on initial belief, observed behavior, and run-time...
QuanTM: A Quantitative Trust Management System (2009)
West, Andrew G, Aviv, Adam J, Chang, Jian, Prabhu, Vinayak S, Blaze, Matthew A, Kannan, Sampath, ...
Quantitative Trust Management (QTM) provides a dynamic interpretation of authorization policies for access control decisions based on upon evolving reputations of the entities involved. QuanTM, a QTM...
Dynamic Trust Management (2009)
Blaze, Matt, Kannan, Sampath, Lee, Insup, Sokolsky, Oleg, Smith, Jonathan M, Keromytis, Angelos D, ...
Trust management forms the basis for communicating policy among system elements and demands credential checking for access to all virtual private service resources--along with careful evaluation of...
Computing Diameter in the Streaming and (2008)
Sliding-window Models, Joan Feigenbaum, Sampath Kannan, Jian Zhang
Abstract We investigate the diameter problem in the streaming and slidingwindow models. We show that, for a stream of n points or a sliding window of size n, any exact algorithm for diameter requires...
Abstract Matching nuts and bolts (Extended Abstract) (2008)
Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky
We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of bolts and nuts and wants to find the corresponding pairs of bolts and nuts. The procedure uses our...
Abstract Reconstructing Strings from Random Traces (2008)
Sampath Kannan, Sanjeev Khanna, Andrew Mcgregor
We are given a collection of m random subsequences (traces) of a string t of length n where each trace is obtained by deleting each bit in the string with probability q. Our goal is to exactly...
L.S.: Genome identification and classification by short oligo arrays (2008)
Stanislav Angelov, Boulos Harb, Sampath Kannan, Junhyong Kim, Li-san Wang
Abstract. We explore the problem of designing oligonucleotides that help locate organisms along a known phylogenetic tree. We develop a suffix-tree based algorithm to find such short sequences...
RV 2005 Preliminary Version Steering of Discrete Event Systems: Control Theory Approach (2008)
Arvind Easwaran, Sampath Kannan, Oleg Sokolsky
Runtime verification involves monitoring the system at runtime to check for conformance of the execution trace to user defined safety properties. Typically, run-time verifiers do not assume a system...
Checking and Spot-Checking the Correctness of Priority Queues (2008)
Matthew Chu, Sampath Kannan, Andrew Mcgregor
Abstract. We revisit the problem of memory checking considered by Blum et al. [3]. In this model, a checker monitors the behavior of a data structure residing in unreliable memory given an arbitrary...
Efficient Enumeration of Phylogenetically Informative Substrings (2008)
Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim
Abstract. We study the problem of enumerating substrings that are common amongst genomes that share evolutionary descent. For example, one might want to enumerate all identical (therefore conserved)...
Abstract Weighted Isotonic Regression under the L1 Norm (2008)
Stanislav Angelov, Boulos Harb, Sampath Kannan, Li-san Wang
Isotonic regression, the problem of finding values that best fit given observations and conform to specific ordering constraints, has found many applications in biomedical research and other fields....
Abstract Matching nuts and bolts (Extended Abstract) (2008)
Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan
We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of bolts and nuts and wants to nd the corresponding pairs of bolts and nuts. The procedure uses our...
A bound on the capacity of backoff and acknowledgement-based protocols (2008)
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson
Abstract. We study contention-resolution protocols for multiple-access channels. We show that every backoff protocol is transient if the arrival rate, λ, is at least 0.42 and that the capacity of...
Randomized Pursuit-Evasion in a Polygonal Environment (2008)
Volkan Isler, Student Member, Sampath Kannan, Sampath Kannan, Sanjeev Khanna, Sanjeev Khanna
This paper contains two main results: First, we revisit the well-known visibility based pursuit-evasion problem and show that, in contrast to deterministic strategies, a single pursuer can locate an...
Security Protocols with Isotropic Channels (2008)
Madhukar Anand Eric, Eric Cronin, Micah Sherr, Matt Blaze, Sampath Kannan
We investigate the security properties of isotropic channels, broadcast media in which a receiver cannot reliably determine whether a message originated from any particular sender and a sender cannot...
Minimizing Space Usage in Evaluation of Expression Trees (2008)
Sandip K. Biswas, Sampath Kannan
. An important issue in the evaluation of expression trees (and more generally, directed acyclic graphs (dags)) is the order in which the nodes of the graph are evaluated. In the register sufficiency...
STCON in Directed Unique-Path Graphs (2008)
Kannan, Sampath, Khanna, Sanjeev, Roy, Sudeepa
We study the problem of space-efficient polynomial-time algorithms for {em directed st-connectivity} (STCON). Given a directed graph $G$, and a pair of vertices $s, t$, the STCON problem is to decide...
Difference Algorithm For, Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
A Formal Framework for Evaluating Heuristic Programs (2007)
Lenore Cowen, Joan Feigenbaum, Sampath Kannan
This paper provides a family of definitions that formalize the notion of a timer and some preliminary results that demonstrate the utility of these definitions.
Difference Algorithm For, Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
A Formal Framework for Evaluating Heuristic Programs (2007)
By Lenore, Lenore Cowen, Joan Feigenbaum, Sampath Kannan
We address the question of how one evaluates the usefulness of a heuristic program on a particular input. If theoretical tools do not allow us to decide for every instance whether a particular...
Joan Feigenbaum, Sampath Kannan, Jian Zhang
Abstract. We investigate the diameter problem in the streaming and sliding-window models. We show that, for a stream of n points or a sliding window of size n, any exact algorithm for diameter...
Run-time Monitoring and Steering based on Formal Specifications* (2007)
Sampath Kannan, Moonjoo Kim, Insup Lee T, Oleg Sokolsky, Mahesh Viswanathan
We describe the Monitoring-aided Checking and Steering (MACS) framework that assures the cor-rectness of software execution at run-time. Check-ing is performed based on a formal specification of...
Bhaskar Dasgupta, Tao Jiang, Sampath Kannan, Ming Li
The paper studies the computational complexity and approximation algorithms for a new evolutionary distance between multi-chromosomal genomes introduced recently by Ferretti, Nadeau and Sankoff....
Funda Ergun, Sampath Kannan, S Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
On Labor Day weekend, the highway patrol sets up spot-checks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
Joan Feigenbaum, Sampath Kannan, Moshe Y. Vardi, Mahesh Viswanathan
To analyze the complexity of decision problems on graphs, one normally assumes that the input size is polynomial in the number of vertices. Galperin and Wigderson [GW83] and, later, Papadimitriou and...
Saumya Debray, David Gudeman, Sampath Kannan
This paper discusses call forwarding, a simple interprocedural optimization technique for dynamically typed languages. The basic idea behind the optimization is straightforward: find an ordering for...
Joan Feigenbaum, Joan Feigenbaum, Siddharth Suri, Siddharth Suri, Sampath Kannan, Sampath Kannan, ...
We investigate the importance of space when solving problems based on graph distance in the streaming model. In this model, the input graph is presented as a stream of edges in an arbitrary order....
Graduate Group Chairperson (2007)
Boulos Harb, Sampath Kannan, Sudipto Guha, Rajeev Alur, Boulos Harb
iii
Graduate Group Chairperson (2007)
Andrew Mcgregor, Sampath Kannan, Rajeev Alur, Andrew Mcgregor
I am fortunate to have learnt a lot from some great people during my time in graduate school. First and foremost, I would like to thank Sampath Kannan for being a fantastic advisor. Talking with...
Simulation-Based Graph Similarity (2006)
Sokolsky, Oleg, Kannan, Sampath, Lee, Insup
We present symmetric and asymmetric similarity measures for labeled directed rooted graphs that are inspired by the simulation and bisimulation relations on labeled transition systems. Computation of...
Randomized Pursuit-Evasion with Local Visibility (2006)
Isler, Volkan, Kannan, Sampath, Khanna, Sanjeev
We study the following pursuit-evasion game: One or more hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gather information about the location of the...
Security Protocols with Isotropic Channels (2006)
Anand, Madhukar, Cronin, Eric, Sherr, Micah, Blaze, Matthew A, Kannan, Sampath
We investigate the security properties of isotropic channels, broadcast media in which a receiver cannot reliably determine whether a message originated from any particular sender and a sender cannot...
Randomized pursuit-evasion with local visibility (2006)
Volkan Isler, Sampath Kannan, Sanjeev Khanna
We study the following pursuit-evasion game: One or more hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gather information about the location of the...
On Graph Problems in a Semi-Streaming Model (2005)
Feigenbaum, Joan, Kannan, Sampath, McGregor, Andrew, Suri, Siddharth, Zhang, Jian
We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive graphs whose...
Optimal Control of Software Ensuring Safety and Functionality (2005)
Easwaran, Arvind, Kannan, Sampath, Lee, Insup
Existing verification and validation methodologies can detect software violations very effectively but fail to provide any mechanism for correcting faults once they are detected. Detection of faults,...
Randomized Pursuit-Evasion in a Polygonal Environment (2005)
Isler, Volkan, Kannan, Sampath, Khanna, Sanjeev
This paper contains two main results. First, we revisit the well-known visibility-based pursuit-evasion problem, and show that in contrast to deterministic strategies, a single pursuer can locate an...
Better Alternatives to OSPF Routing (2005)
Strauss, Martin J., Gilbert, Anna C., Fong, Jessica H., Kannan, Sampath
The current standard for intra-domain network routing, Open ShortestPath First (OSPF), suffers from a number ofproblems-the tunable parameters (the weights) are hard tooptimize, the chosen paths are...
Steering of Discrete Event Systems: Control Theory Approach (2005)
Easwaran, Arvind, Kannan, Sampath, Sokolsky, Oleg
Runtime verification involves monitoring the system at runtime to check for conformance of the execution trace to user defined safety properties. Typically, run-time verifiers do not assume a system...
Graph distances in the streaming model: the value of space (2005)
Joan Feigenbaum, Sampath Kannan, Andrew Mcgregor, Siddharth Suri, Jian Zhang
We investigate the importance of space when solving problems based on graph distance in the streaming model. In this model, the input graph is presented as a stream of edges in an arbitrary order....
Java-MaC: A Run-time Assurance Approach for Java Programs (2004)
Kim, Moonjoo, Viswanathan, Mahesh, Kannan, Sampath, Lee, Insup, Sokolsky, Oleg V
We describe Java-MaC, a prototype implementation of the Monitoring and Checking (MaC) architecture for Java programs. The MaC architecture provides assurance that the target program is running...
Reconstructing strings from random traces (2004)
Batu, Tugkan, Kannan, Sampath, Khanna, Sanjeev, McGregor, Andrew
Reconstructing Strings from Random Traces (2004)
Batu, Tugkan, Kannan, Sampath, Khanna, Sanjeev, McGregor, Andrew
We are given a collection of m random subsequences (traces) of a string t of length n where each trace is obtained by deleting each bit in the string with probability q. Our goal is to exactly...
On graph problems in a semi-streaming model (2004)
Joan Feigenbaum, Sampath Kannan, Andrew Mcgregor, Jian Zhang
Abstract. We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive...
On graph problems in a semi-streaming model (2004)
Joan Feigenbaum, Sampath Kannan, Andrew Mcgregor, Jian Zhang
Abstract. We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of ecient algorithms for solving problems on massive...
and P.Valtr. VC-dimension of exterior visibility (2004)
Volkan Isler, Sampath Kannan, Kostas Daniilidis, Pavel Valtr
In this paper, we study the Vapnik-Chervonenkis (VC)-dimension of set systems arising in 2D polygonal and 3D polyhedral configurations where a subset consists of all points visible from one camera....
Algorithms for Distributed and Mobile Sensing (2004)
Ibrahim Volkan Isler, Benjamin Pierce, Kostas Daniilidis, Kostas Daniilidis, ...
ALGORITHMS FOR DISTRIBUTED AND MOBILE SENSING Ibrahim Volkan Is . ler Kostas Daniilidis and Sampath Kannan Sensing remote, complex and large environments is an important task that arises in diverse...
Sampling Based Sensor-Network Deployment (2004)
Volkan Isler, Sampath Kannan, Kostas Daniilidis
In this paper, we consider the problem of placing networked sensors in a way that guarantees coverage and connectivity. We focus on sampling based deployment and present algorithms that guarantee...
Randomized pursuit-evasion with limited visibility (2004)
Volkan Isler, Sampath Kannan, Sanjeev Khanna
Abstract We study the following pursuit-evasion game: One ormore hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gatherinformation about the location...
Locating and Capturing an Evader in a Polygonal Environment (2004)
Volkan Isler, Sampath Kannan, Sanjeev Khanna
This paper contains two main results: First, we revisit the well-known visibility based pursuit-evasion problem and show that, in contrast to deterministic strategies, a single pursuer can locate an...
Randomized Pursuit-Evasion with Limited Visibility (2004)
Volkan Isler, Sampath Kannan, Sanjeev Khanna
We study the following pursuit-evasion game: One or more hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gather information about the location of the...
Randomized Pursuit-Evasion with Limited Visibility (2004)
Volkan Isler, Sampath Kannan, Sanjeev Khanna
We study the following pursuit-evasion game: One or more hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gather information about the location of the...
Selection with Monotone Comparison Costs (2003)
Kannan, Sampath, Khanna, Sanjeev
We consider the problem of selecting the rth -smallest element from a list of nelements under a model where the comparisons may have different costs depending on the elements being compared. This...
Randomized Pursuit-Evasion with Limited Visibility (2003)
Isler, Volkan, Kannan, Sampath, Khanna, Sanjeev
We study the following pursuit-evasion game: One or more hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gather information about the location of the...
Locating and Capturing an Evader in a Polygonal Environment (2003)
Isler, Volkan, Kannan, Sampath, Khanna, Sanjeev
This paper contains two main results: First, we revisit the well-known visibility based pursuit-evasion problem and show that, in contrast to deterministic strategies, a single pursuer can locate an...
Leslie Ann Goldberg, Sampath Kannan, Mark Jerrum, Mike Paterson
We study contention-resolution protocols for multiple-access channels. We show that every backoff protocol is transient if the arrival rate, λ, is at least 0.42 and that the capacity of every...
Local exploration: Online algorithms and a probabilistic framework (2003)
Volkan Isler, Sampath Kannan, Kostas Daniilidis
Abstract — Mapping an environment with an imaging sensor becomes very challenging if the environment to be mapped is unknown and has to be explored. Exploration involves the planning of views so...
Selection with Monotone Comparison Costs (2003)
Sampath Kannan, Sanjeev Khanna
We consider the problem of selecting the r -smallest element from a list of n elements under a model where the comparisons may have different costs depending on the elements being compared. This...
Computational Analysis of Run-time Monitoring: Fundamentals of Java-MaC (2002)
Kim, Moonjoo, Kannan, Sampath, Lee, Insup, Sokolsky, Oleg, Viswanathan, Mahesh
A run-time monitor shares computational resources, such as memory and CPU time, with the target program. Furthermore, heavy computation performed by a monitor for checking target program's execution...
Computing Diameter in the Streaming and Sliding-Window Models (2002)
Joan Feigenbaum, Sampath Kannan, Jian Zhang
We investigate the diameter problem in the streaming and sliding-window models. We show that, for a stream of n points or a sliding window of size n, any exact algorithm for diameter requires Ω(n)...
Computing Diameter in the Streaming and Sliding-Window Models (2002)
Joan Feigenbaum, Sampath Kannan, Jian Zhang
We investigate the diameter problem in the streaming and sliding-window models. We show that, for a stream of n points or a sliding window of size n, any exact algorithm for diameter requires Ω(n)...
Inferring mixtures of markov chains (2002)
Abstract. We define the problem of inferring a “mixture of Markov chains ” based on observing a stream of interleaved outputs from these chains. We show a sharp characterization of the inference...
An Approximate L¹-Difference Algorithm for Massive Data Streams (2002)
Joan Feigenbaum, Sampath Kannan, Martin J. Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, includingobservational sciences, product marketing, and the monitoring and operations of large systems. In network...
Computational Analysis of Run-time Monitoring - Fundamentals of Java-MaC (2002)
Moonjoo Kim, Sampath Kannan, Insup Lee, Oleg Sokolsky, Mahesh Viswanathan
A run-time monitor shares computational resources, such as memory and CPU time, with the target program. Furthermore, heavy computation performed by a monitor for checking target program's...
VC-Dimension of Exterior Visibility of Polyhedra (2001)
Isler, Volkan, Kannan, Sampath, Daniilidis, Kostas
In this paper, we address the problem of finding the minimal number of viewpoints outside a polyhedron in two or three dimensions such that every point on the exterior of the polyhedron is visible...
VC-dimension of exterior visibility of polyhedra (2001)
Volkan Isler, Sampath Kannan, Kostas Daniilidis
In this paper, we address the problem of finding the minimal number of viewpoints outside a polyhedron in two or three dimensions such that every point on the exterior of the polyhedron is visible...
Formal Analysis of Routing Protocols (2001)
Val Tannen, G. Grin, F. Bruce Shepherd, Gordon Wilfong, Lixin Gao, Dimosthenis Anthomelidis, ...
thank them for the inspiration they provided. I would like to thank the CISCO Corporation, and especially Alvaro Retana, for supporting my research on BGP. I would also like to thank Rajeev
Testing and spot-checking of data streams (2000)
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
We consider the tasks of testing and spot-checking for data streams. These testers and spotcheckers are potentially useful in real-time or near real-time applications that process huge datasets....
Testing and Spot-Checking of Data Streams (2000)
Joan Feigenbaum Att, Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
We consider the tasks of testing and spot-checking for data streams. These testers and spotcheckers are potentially useful in real-time or near real-time applications that process huge datasets....
A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols (2000)
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Goldberg Mark, Jerrum Sampath Kannan, Mike Paterson
We study contention-resolution protocols for multiple-access channels. We show that every backo protocol is transient if the arrival rate, , is at least 0:42 and that the capacity of every backo...
Testing and Spot-Checking of Data Streams (2000)
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
We consider the tasks of testing and spot-checking for data streams. These testers and spotcheckers are potentially useful in real-time or near real-time applications that process huge datasets....
Dynamic Graph Algorithms (2000)
Joan Feigenbaum, Sampath Kannan
INTRODUCTION Dynamic graph algorithms are algorithms that maintain properties of a (possibly edgeweighted) graph while the graph is changing. These algorithms are potentially useful in a number of...
Runtime Assurance Based On Formal Specifications (1999)
Lee, Insup, Kannan, Sampath, Kim, Moonjoo, Sokolsky, Oleg, Viswanathan, Mahesh
We describe the Monitoring and Checking (MaC) framework which assures the correctness of the current execution at run-time. Monitoring is performed based on a formal specification of system...
Formally Specified Monitoring of Temporal Properties (1999)
Kim, Moonjoo, Viswanathan, Mahesh, Ben-Abdallah, Hanene, Kannan, Sampath, Lee, Insup, Sokolsky, Oleg
We describe the Monitoring and Checking (MaC) framework which provides assurance on the correctness of an execution of a real-time system at run-time. Monitoring is performed based on a formal...
An approximate L 1 -dierence algorithm for massive data streams (1999)
Joan Feigenbaum, Sampath Kannan, Martin J. Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
Formally Specified Monitoring of Temporal Properties (1999)
Moonjoo Kim, Mahesh Viswanathan, Hanêne Ben-Abdallah, Sampath Kannan, Insup Lee, Oleg Sokolsky
We describe the Monitoring and Checking (MaC) framework which provides assurance on the correctness of an execution of a real-time system at runtime. Monitoring is performed based on a formal...
An Approximate L¹-Difference Algorithm for Massive Data Streams (1999)
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
Tight Bounds on the Learnability of Evolution (1999)
Andris Ambainis, Richard Desper, Martin Farach-colton, Sampath Kannan
Evolution is often modeled as a stochastic process which modifies DNA. One of the most popular such processes are the Cavender-Farris (CF) trees, which are represented as edge weighted trees. The...
MaC: A Framework for Run-time Correctness Assurance of Real-Time Systems (1999)
Moonjoo Kim, Mahesh Viswanathan, Hanêne Ben-Abdallah, Sampath Kannan, Insup Lee, Oleg Sokolsky
We describe the Monitoring and Checking (MaC) framework which provides assurance on the correctness of program execution at run-time. Our approach complements the two traditional approaches for...
An Approximate L 1 -Difference Algorithm for Massive Data Streams (1999)
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
Testing and Spot-Checking of Data Streams (1999)
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
We consider the tasks of testing and spot-checking for data streams. These testers and spotcheckers are potentially useful in real-time or near real-time applications that process huge datasets....
Streaming Algorithms for Distributed, Massive Data Sets (1999)
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
Communicating Hierarchical State Machines (1999)
Rajeev Alur, Sampath Kannan, Mihalis Yannakakis
. Hierarchical state machines are finite state machines whose states themselves can be other machines. In spite of their popularity in many modeling tools for software design, very little is known...
Polyhedral Flows in Hybrid Automata (1999)
Rajeev Alur, Sampath Kannan, Salvatore La Torre
A hybrid automaton is a mathematical model for hybrid systems, which combines, in a single formalism, automaton transitions for capturing discrete updates with differential constraints for capturing...
Ronitt Rubinfeld, Sampath Kannan, Mahesh Viswanathan, S Ravi Kumar
On Labor Day weekend, the highway patrol sets up spot-checks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
Checkers, Self-Testers, and Self-Correctors for Reactive Systems (1998)
This report discusses the development of formal methods for monitoring safety-critical real-time and reactive systems. This project centers on building on expertise in the area of...
A Monitoring and Checking Framework for Run-time Correctness Assurance (1998)
Lee, Insup, Ben-Abdallah, Hanene, Kannan, Sampath, Kim, Moonjoo, Sokolsky, Oleg, Viswanathan, Mahesh
Computer systems are often monitored for performance evaluation and enhancement, debugging and testing, control or to check for the correctness of the system. Recently, the problem of designing...
MaC: A Framework for Run-time Correctness Assurance of Real-Time Systems (1998)
Kim, Moonjoo, Viswanathan, Mahesh, Ben-Abdallah, Hanene, Kannan, Sampath, Lee, Insup, Sokolsky, Oleg
We describe the Monitoring and Checking (MaC) framework which provides assurance on the correctness of program execution at run-time. Our approach complements the two traditional approaches for...
Funda Ergun Sampath, Sampath Kannan, S Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
On Labor Day weekend, the highway patrol sets up spot-checks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
Efficient Algorithms for Inverting Evolution (1998)
Evolution can be mathematically modelled by a stochastic process that operates on the DNA of species. Such models are based on the established theory that the DNA sequences (or genomes) of all extant...
Funda Ergun Sampath, Sampath Kannan, S Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
On Labor Day weekend, the highway patrol sets up spot-checks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
Polyhedral Flows in Hybrid Automata (1998)
Rajeev Alur, Sampath Kannan, Salvatore La Torre
A hybrid automaton is a mathematical model for hybrid systems, which combines, in a single formalism, automaton transitions for capturing discrete updates with differential constraints for capturing...
Funda Ergun, Sampath Kannan, S Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
On Labor Day Weekend, the highway patrol sets up spotchecks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
Computing the Local Consensus of Trees (1998)
Sampath Kannan, Tandy Warnow, Shibu Yooseph
.<F3.815e+05> The inference of consensus from a set of evolutionary trees is a fundamental problem in a number of fields such as biology and historical linguistics, and many models for...
Funda Ergun, Sampath Kannan, S Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan
On Labor Day Weekend, the highway patrol sets up spotchecks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very...
A Fast Algorithm For The Computation And Enumeration Of Perfect Phylogenies (1997)
.<F3.813e+05> The perfect phylogeny problem is a classical problem in computational evolutionary biology, in which a set of species/taxa is described by a set of qualitative characters. In...
On the Complexity and Approximation of Syntenic Distance (1997)
Bhaskar Dasgupta, Tao Jiang, Sampath Kannan, Ming Li
The paper studies the computational complexity and approximation algorithms for a new evolutionary distance between multi-chromosomal genomes introduced recently by Ferretti, Nadeau and Sankoff....
Efficient algorithms for inverting evolution (1996)
Evolution can be mathematically modelled by a stochastic process that operates on the DNA of species. Such models are based on the established theory that the DNA sequences, or genomes, of all extant...
Oracles and queries that are sufficient for exact learning (1996)
Nader H. Bshouty, Richard Cleve, Sampath Kannan, Christino Tamon
We show that the class of all circuits is exactly learnable in randomized expected polynomial time using weak subset and weak superset queries. This is a consequence of the following result which we...
Oracles and Queries that are Sufficient for Exact Learning (1996)
Nader Bshouty Richard, Richard Cleve, Sampath Kannan, Christino Tamon
We show that the class of all circuits is exactly learnable in randomized expected polynomial time using weak subset and weak superset queries. This is a consequence of the following result which we...
Oracles and Queries that are Sufficient for Exact Learning (1996)
Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, Christino Tamon
We show that the class of all circuits is exactly learnable in randomized expected polynomial time using subset and superset queries. This is a consequence of the following result which we consider...
Efficient Algorithms for Inverting Evolution (1996)
Evolution is a stochastic process which operates on the DNA of species. The evolutionary process leaves tell-tale signs in the DNA which can be used to construct phylogenies, or evolutionary trees,...
A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies (1996)
The Perfect Phylogeny Problem is a classical problem in computational evolutionary biology, in which a set of species/taxa is described by a set of qualitative characters. In recent years, the...
Computing the local consensus of trees (1995)
Sampath Kannan, Tandy Warnow, Shibu Yooseph
Abstract. The inference of consensus from a set of evolutionary trees is a fundamental problem in a number of fields such as biology and historical linguistics, and many models for inferring this...
A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies (1995)
Sampath Kannan Tandy, Sampath Kannan, Tandy Warnow
The Perfect Phylogeny Problem is a classical problem in computational evolutionary biology, in which a set of species/taxa is described by a set of qualitative characters. In recent years, the...
Efficient Algorithms for Inverting Evolution (1995)
Evolution is a stochastic process which operates on the DNA of species. The evolutionary process leaves tell-tale signs in the DNA which can be used to construct phylogenies, or evolutionary trees,...
A Quasi-Polynomial-Time Algorithm for Sampling Words From a Context-Free Language (1995)
Vivek Gore, Mark Jerrum, Sampath Kannan, Z. Sweedyk, Steve Mahaney
A quasi-polynomial-time algorithm is presented for sampling almost uniformly at random from the n-slice of the language L(G) generated by an arbitrary context-free grammar G. (The n-slice of a...
Computing the Local Consensus of Trees (1995)
Sampath Kannan, Tandy Warnow, Shibu Yooseph
The inference of consensus from a set of evolutionary trees is a fundamental problem in a number of fields, such as biology and historical linguistics, and many models for inferring this consensus...
A Formal Framework for Evaluating Heuristic Programs (1995)
By Lenore, Lenore Cowen, Joan Feigenbaum, Sampath Kannan
We address the question of how one evaluates the usefulness of a heuristic program on a particular input. If theoretical tools do not allow us to decide for every instance whether a particular...
Register Allocation in Structured Programs (1995)
Sampath Kannan, Todd Proebsting, Contact Name, Sampath K. Kannan
In this paper we look at the register allocation problem. In the literature this problem is frequently reduced to the general graph coloring problem and the solutions to the problem are obtained from...
Designing programs that check their work (1995)
A program correctness checker is an algorithm for checking the output of a computation. This paper defines the concept of a program checker. It designs program checkers for a few specific and...
ORACLES AND QUERIES THAT ARE SUFFICIENT FOR EXACT LEARNING (1994)
Bshouty, Nader H., Cleve, Richard, Tamon, Christino, Kannan, Sampath
We show that the class of all circuits is exactly learnable in (randomized) expected polynomial-time using subset and superset queries. Subset and superset queries are a generalization of equivalence...
ORACLES AND QUERIES THAT ARE SUFFICIENT FOR EXACT LEARNING (1994)
Bshouty, Nader H., Cleve, Richard, Tamon, Christino, Kannan, Sampath
We show that the class of all circuits is exactly learnable in (randomized) expected polynomial-time using subset and superset queries. Subset and superset queries are a generalization of equivalence...
ORACLES AND QUERIES THAT ARE SUFFICIENT FOR EXACT LEARNING (1994)
Bshouty, Nader H., Cleve, Richard, Tamon, Christino, Kannan, Sampath
We show that the class of all circuits is exactly learnable in (randomized) expected polynomial-time using subset and superset queries. Subset and superset queries are a generalization of equivalence...
Checking the correctness of memories (1994)
Manuel Blum, Will Evans, Peter Gemmell, Sampath Kannan, Moni Naor
We extend the notion of program checking to include programs which alter their environment. In particular, we consider programs which store and retrieve data from memory. The model we consider allows...
Matching Nuts and Bolts (Extended Abstract) (1994)
Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky
) Noga Alon y Manuel Blum z Amos Fiat x Sampath Kannan -- Moni Naor k Rafail Ostrovsky Abstract We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of...
Oracles and Queries that are Sufficient for Exact Learning (1994)
Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, Christino Tamon
We show that the class of all circuits is exactly learnable in randomized expected polynomial time using weak subset and weak superset queries. This is a consequence of the following result which we...
Checking the Correctness of Memories (1994)
Manuel Blum, Will Evans, Peter Gemmell, Sampath Kannan, Moni Naor
We extend the notion of program checking to include programs which alter their environment. In particular, we consider programs which store and retrieve data from memory. The model we consider allows...
Koen De Bosschere, Saumya K. Debray, David Gudeman, Sampath Kannan
This paper discusses call forwarding, a simple interprocedural optimization technique for dynamically typed languages. The basic idea behind the optimization is straightforward: find an ordering for...
Matching Nuts and Bolts (1994)
Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky
) Noga Alon Manuel Blum y Amos Fiat z Sampath Kannan x Moni Naor -- Rafail Ostrovsky k Abstract We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of...
Checking the Correctness of Memories (1994)
Manuel Blum, Will Evans, Peter Gemmell, Sampath Kannan, Moni Naor
Program checking has been thought of merely as checking the computation of a function which does not have any side effects. We extend the notion of program checking to include programs which alter...
Matching Nuts and Bolts (1993)
Exte Nd Ed, Noga Alon, Manuel Blum, Sampath Kannan, Moni Naor, Rafail Ostrovsky
) Noga Alon y Manuel Blum z Amos Fiat x Sampath Kannan -- Moni Naor k Rafail Ostrovsky TR-93-075 Novemeber, 1993 Abstract We describe a procedure which may be helpful to any disorganized carpenter...
A Robust Model for Finding Optimal Evolutionary Trees (1993)
Martin Farach Sampath, Martin Farach, Sampath Kannan, Tandy Warnow
Constructing evolutionary trees for species sets is a fundamental problem in computational biology. One of the standard models assumes the ability to compute distances between every pair of species...
A Robust Model for Finding Optimal Evolutionary Trees (1993)
Martin Farach, Sampath Kannan, Tandy Warnow
Constructing evolutionary trees for species sets is a fundamental problem in computational biology. One of the standard models assumes the ability to compute distances between every pair of species...
Implicit representation of graphs (1992)
Sampath Kannan, Moni Naor, Steven Rudich
How to represent a graph in memory is a fundamental data structuring question. In the usual representations of an n-vertex graph, the names of the vertices (i.e. integers from 1 to n) betray nothing...
Weighted Decision Trees (1992)
Saumya Debray, Sampath Kannan, Mukul Paithane
Abstract: While decision tree compilation is a promising way to carry out guard tests efficiently, the methods given in the literature do not take into account either the execution characteristics of...
We define and study the graph-theoretic notion of an anchor in a tournament. An anchor in a tournament is a subset of the nodes of the tournament such that every pair of nodes outside the anchor is...
Program Checkers for Probability Generation (1991)
this paper we will restrict attention to the uniform model defined above.
Lower Bounds on Random-Self-Reducibility (Extended Abstract) (1990)
Joan Feigenbaum, Sampath Kannan, Noam Nisan
Structures-1990 Proceedings) Joan Feigenbaum Sampath Kannan y Noam Nisan z Abstract: Informally speaking, a function f is random-self-reducible if, for any x, the computation of f(x) can be reduced...
Designing Programs That Check Their Work (1989)
Manuel Blum, Sampath Kannan, Comp Sci, Comp Sci
A program correctness checker is an algorithm for checking the output of a computation. That is, given a program and an instance on which the program is run, the checker certifies whether the output...
Joan Feigenbaum, Sampath Kannan, Andrew Mcgregor, Siddharth Suri, Jian Zhang
Abstract. We explore problems related to computing graph distances in the data-stream model. The goal is to design algorithms that can process the edges of a graph in an arbitrary order given only a...