Kannan, Sampath
Email Address
ORCID
Disciplines
relationships.isProjectOf
relationships.isOrgUnitOf
Position
Introduction
Research Interests
Collection
36 results
Search Results
Now showing 1 - 10 of 36
Publication Selection with Monotone Comparison Costs(2003-01-12) Kannan, Sampath; Khanna, SanjeevWe 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 model was introduced by [3] and is realistic in the context of comparisons between complex objects. An important special case of this general cost model is one where the comparison costs are monotone in the sizes of the elements being compared. This monotone cost model covers most "natural" cost models that arise and the selection problem turns out to be the most challenging one among the usual problems for comparison-based algorithms. We present an O(log2 n)-competitive algorithm for selection under the monotone cost model. This is in contrast to an Ω (n)lower bound that is known for arbitrary comparison costs. We also consider selection under a special case of monotone costs—-the min model where the cost of comparing two elements is the minimum of the sizes. We give a randomized O(1)-competitive algorithm for the min model.Publication VC-Dimension of Exterior Visibility of Polyhedra(2001-01-01) Kannan, Sampath; Isler, Volkan; Daniilidis, KostasIn 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 from at least one of the chosen viewpoints. This problem which we call the minimum fortress guard problem (MFGP) is the optimization version of a variant of the art-gallery problem (sometimes called the fortress problem with point guards) and has practical importance in surveillance and image-based rendering. Solutions in the vision and graphics literature are based on image quality constraints and are not concerned with the number of viewpoints needed. The corresponding question for art galleries (minimum number of viewpoints in the interior of a polygon to see the interior of the polygon) which we call the minimum art-gallery guard problem (MAGP) has been shown to be NP-complete. A simple reduction from this problem shows the NP-completeness of MFGP. Instead of relying on heuristic searches, we address the approximability of the camera placement problem. It is well known (and easy to see) that this problem can be cast as a hitting set problem. While the approximability of generic instances of the hitting set problem is well understood, Brönnimann and Goodrich[3] presented improved approximation algorithms for the problem in the case that the input instances have bounded Vapnik-Chervonenkis (VC) dimension. In this paper we explore the VC-dimension of set systems associated with the camera placement problem described above. We show a constant bound for the VC dimension in the two dimensional case but a tight logarithmic bound in the three dimensional case. In the two dimensional case we are also able to present an algorithm that uses at most one more viewpoint than the optimal in the case that the viewpoints are restricted to be on a circumscribing circle - a restriction that is justified in practice.Publication Algorithms for the Generalized Sorting Problem(2011-10-01) Kannan, Sampath; Huang, Zhiyi; Khanna, SanjeevWe study the generalized sorting problem where we are given a set of n elements to be sorted but only a subset of all possible pairwise element comparisons is allowed. The goal is to determine the sorted order using the smallest possible number of allowed comparisons. The generalized sorting problem may be equivalently viewed as follows. Given an undirected graph G(V,E) where V is the set of elements to be sorted and E defines the set of allowed comparisons, adaptively find the smallest subset E' E of edges to probe such that the directed graph induced by E' contains a Hamiltonian path. When G is a complete graph, we get the standard sorting problem, and it is well-known that Θ(n log n) comparisons are necessary and sufficient. An extensively studied special case of the generalized sorting problem is the nuts and bolts problem where the allowed comparison graph is a complete bipartite graph between two equal-size sets. It is known that for this special case also, there is a deterministic algorithm that sorts using Θ(n log n) comparisons. However, when the allowed comparison graph is arbitrary, to our knowledge, no bound better than the trivial O(n2) bound is known. Our main result is a randomized algorithm that sorts any allowed comparison graph using Õ(n3⁄2) comparisons with high probability (provided the input is sortable). We also study the sorting problem in randomly generated allowed comparison graphs, and show that when the edge probability is p, Õ(min{n/p2 , n3⁄2p √p}) comparisons suffice on average to sort.Publication QuanTM: A Quantitative Trust Management System(2009-03-01) West, Andrew G; Aviv, Adam J; Chang, Jian; Prabhu, Vinayak S; Blaze, Matthew A; Kannan, Sampath; Lee, Insup; Smith, Jonathan M; Sokolsky, OlegQuantitative 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 system, selectively combines elements from trust management and reputation management to create a novel method for policy evaluation. Trust management, while effective in managing access with delegated credentials (as in PolicyMaker and KeyNote), needs greater flexibility in handling situations of partial trust. Reputation management provides a means to quantify trust, but lacks delegation and policy enforcement. This paper reports on QuanTM’s design decisions and novel policy evaluation procedure. A representation of quantified trust relationships, the trust dependency graph, and a sample QuanTM application specific to the KeyNote trust management language, are also proposed.Publication Reconstructing Strings from Random Traces(2004-01-11) Kannan, Sampath; Batu, Tugkan; Khanna, Sanjeev; McGregor, AndrewWe 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 reconstruct the string t from these observed traces. We initiate here a study of deletion rates for which we can successfully reconstruct the original string using a small number of samples. We investigate a simple reconstruction algorithm called Bitwise Majority Alignment that uses majority voting (with suitable shifts) to determine each bit of the original string. We show that for random strings t, we can reconstruct the original string (w.h.p.) for q = O(1/ log n) using only O(log n) samples. For arbitrary strings t, we show that a simple modification of Bitwise Majority Alignment reconstructs a string that has identical structure to the original string (w.h.p.) for q = O(1/n1/2+ε) using O(1) samples. In this case, using O(n log n) samples, we can reconstruct the original string exactly. Our setting can be viewed as the study of an idealized biological evolutionary process where the only possible mutations are random deletions. Our goal is to understand at what mutation rates, a small number of observed samples can be correctly aligned to reconstruct the parent string. In the process of establishing these results, we show that Bitwise Majority Alignment has an interesting selfcorrecting property whereby local distortions in the traces do not generate errors in the reconstruction and eventually get corrected.Publication A Retrospective Look at the Monitoring and Checking (MaC) Framework(2019-10-01) Kannan, Sampath; Lee, Insup; Sokolsky, Oleg; Kim, Moonzoo; Viswanathan, MaheshThe Monitoring and Checking (MaC) project gave rise to a framework for runtime monitoring with respect to formally specified properties, which later came to be known as runtime verification. The project also built a pioneering runtime verification tool, Java-MaC, that was an instantiation of the approach to check properties of Java programs. In this retrospective, we discuss decisions made in the design of the framework and summarize lessons learned in the course of the project.Publication Graph Distances in the Data-Stream Model(2008-12-19) Feigenbaum, Joan; Kannan, Sampth; Mcgregor, Andrew; Suri, Siddarth; Zhang, JianWe 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 limited amount of working memory. We are motivated by both the practical challenge of processing massive graphs such as the web graph and the desire for a better theoretical understanding of the data-stream model. In particular, we are interested in the trade-offs between model parameters such as per-data-item processing time, total space, and the number of passes that may be taken over the stream. These trade-offs are more apparent when considering graph problems than they were in previous streaming work that solved problems of a statistical nature. Our results include the following: (1) Spanner construction: There exists a single-pass, (O) over tilde (tn(1+1/t))-space, (O) over tilde (t(2)n(1/t))-time-per-edge algorithm that constructs a (2t + 1)-spanner. For t = Omega(log n/log log n), the algorithm satisfies the semistreaming space restriction of O(n polylog n) and has per-edge processing time O(polylog n). This resolves an open question from [J. Feigenbaum et al., Theoret. Comput. Sci., 348 (2005), pp. 207-216]. (2) Breadth-first-search (BFS) trees: For any even constant k, we show that any algorithm that computes the first k layers of a BFS tree from a prescribed node with probability at least 2/3 requires either greater than k/2 passes or Omega(n(1+1/k)) space. Since constructing BFS trees is an important subroutine in many traditional graph algorithms, this demonstrates the need for new algorithmic techniques when processing graphs in the data-stream model. (3) Graph-distance lower bounds: Any t-approximation of the distance between two nodes requires Omega(n(1+1/t)) space. We also prove lower bounds for determining the length of the shortest cycle and other graph properties. (4) Techniques for decreasing per-edge processing: We discuss two general techniques for speeding up the per-edge computation time of streaming algorithms while increasing the space by only a small factor.Publication Optimal Control of Software Ensuring Safety and Functionality(2005-10-11) Kannan, Sampath; Easwaran, Arvind; Lee, InsupExisting 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, their diagnosis and corrective actions are all essential components of any software rectification framework. In this paper, we propose a framework for correction of violations in software systems ensuring that the desired goals of the system are achieved. We describe a stochastic finite state machine used to abstract a software system along with the uncertainty in its operating environment. Safety property violations and satisfaction of functionalities are abstracted using penalties and rewards on the states, respectively. Rectification of software is then formulated as a stochastic optimal control problem over this abstraction. Algorithms polynomial in the size of the abstraction have been developed for solving this optimization problem exactly. The paper also applies the developed framework to a variety of examples from different domains.Publication Spatio-Temporal Analysis of Wikipedia Metadata and the STiki Anti-Vandalism Tool(2010-07-01) West, Andrew G.; Kannan, Sampath; Lee, InsupThe bulk of Wikipedia anti-vandalism tools require natural language processing over the article or diff text. However, our prior work demonstrated the feasibility of using spatio-temporal properties to locate malicious edits. STiki is a real-time, on-Wikipedia tool leveraging this technique. The associated poster reviews STiki's methodology and performance. We find competing anti-vandalism tools inhibit maximal performance. However, the tool proves particularly adept at mitigating long-term embedded vandalism. Further, its robust and language-independent nature make it well-suited for use in less-patrolled Wiki installations.Publication Security Protocols With Isotropic Channels(2006-01-01) Anand, Madhukar; Cronin, Eric; Sherr, Micah; Blaze, Matthew A; Kannan, SampathWe 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 reliably direct a message away from any particular receiver. We show that perfect isotropism implies perfect (information-theoretic) secrecy, and that asymptotically close to perfect secrecy can be achieved on any channel that provides some (bounded) uncertainty as to sender identity. We give isotropic security protocols under both passive and active adversary models, and discuss the practicality of realizing isotropic channels over various media.