ETD at Indian Institute of Science
Repository of Theses and Dissertations of Indian Institute of Science, Bangalore, India. The repository has been developed to capture, disseminate and preserve research theses of Indian Institute of Science.
Computer Science and Automation (csa)
Mostrando recursos 1 - 20 de 124
Network Centrality Measures And Their Applications - Sudarshan, S R
Study of complex networks by researchers from many disciplines has provided penetrating insights on various complex systems. A study of the world wide web from a network theoretic perspective has led to the design of new search engines . The spread of diseases is now better understood by analyzing the underlying social network . The study of metabolic networks, protein-protein interaction networks and the transcriptional regulatory networks with graph theoretic rigor, has led to the growing importance of an interdisciplinary approach .
Network centrality measures, which has been of interest to the social scientists, from as long as 1950 ,...
Image Structures For Steganalysis And Encryption - Suresh, V
In this work we study two aspects of image security: improper usage and illegal access of images. In the first part we present our results on steganalysis – protection against improper usage of images. In the second part we present our results on image encryption – protection against illegal access of images.
Steganography is the collective name for methodologies that allow the creation of invisible –hence secret– channels for information transfer. Steganalysis, the counter to steganography, is a collection of approaches that attempt to detect and quantify the presence of hidden messages in cover media.
First we present our studies...
Acyclic Edge Coloring Of Graphs - Basavaraju, Manu
A proper edge coloring of G =(V,E)is a map c : E → C (where C is the set of available colors ) with c(e) ≠ c(ƒ) for any adjacent edges e,f. The minimum number of colors needed to properly color the edges of G, is called the chromatic index of Gand is denoted by χ(G).
A proper edge coloring c is called acyclic if there are no bichromatic cycles in the graph. In other words an edge coloring is acyclic if the union of any two color classes induces a set of paths (i.e., linear forest) in G. The...
Cluster Identification : Topic Models, Matrix Factorization And Concept Association Networks - Arun, R
The problem of identifying clusters arising in the context of topic models and related approaches is important in the area of machine learning. The problem concerning traversals on Concept Association Networks is of great interest in the area of cognitive modelling. Cluster identification is the problem of finding the right number of clusters in a given set of points(or a dataset) in different settings including topic models and matrix factorization algorithms. Traversals in Concept Association Networks provide useful insights into cognitive modelling and performance. First, We consider the problem of authorship attribution of stylometry and the problem of cluster identification...
Low Power Test Methodology For SoCs : Solutions For Peak Power Minimization - Tudu, Jaynarayan Thakurdas
Power dissipated during scan testing is becoming increasingly important for today’s very complex sequential circuits. It is shown that the power dissipated during test mode operation is in general higher than the power dissipated during functional mode operation, the test mode average power may sometimes go upto 3x and the peak power may sometimes go upto 30x of normal mode operation. The power dissipated during the scan operation is primarily due to the switching activity that arises in scan cells during the shift and capture operation. The switching in scan cells propagates to the combinational block of the circuit during...
Generalizations Of The Popular Matching Problem - Nasre, Meghana
Matching problems arise in several real-world scenarios like assigning posts to applicants, houses to trainees and room-mates to one another. In this thesis we consider the bipartite matching problem where one side of the bipartition specifies preferences over the other side. That is, we
are given a bipartite graph G = (A ∪ P,E) where A denotes the set of applicants, P denotes the set of posts, and the preferences of applicants are specified by ranks on the edges. Several notions of optimality like pareto-optimality, rank-maximality, popularity have been studied in the literature; we focus on the notion of popularity. A...
On Dimensional Parameters Of Graphs And Posets - Adiga, Abhijin
In this thesis we study the following dimensional parameters : boxicity, cubicity, threshold dimension and poset dimension. While the ﬁrst three parameters are defined on graphs, poset dimension is defined on partially ordered sets (or posets). We only consider finite graphs and posets. In addition, we assume that the graphs are simple and undirected.
Boxicity and Cubicity: A k-box (k-cube) is a Cartesian product of closed intervals(unit-intervals) [a1,b1]x…x [ak,bk]. The boxicity (cubicity) of a graph G,box (G) (cub(G)) is the minimum integer k such that every vertex in G is mapped to a k-box(k-cube) in the k-dimensional Euclidean space and...
Sparse Multiclass And Multi-Label Classifier Design For Faster Inference - Bapat, Tanuja
Many real-world problems like hand-written digit recognition or semantic scene classiﬁcation are treated as multiclass or multi-label classiﬁcation prob-lems. Solutions to these problems using support vector machines (SVMs) are well studied in literature. In this work, we focus on building sparse max-margin classiﬁers for multiclass and multi-label classiﬁcation. Sparse representation of the resulting classiﬁer is important both from eﬃcient training and fast inference viewpoints. This is true especially when the training and test set sizes are large.Very few of the existing multiclass and multi-label classiﬁcation algorithms have given importance to controlling the sparsity of the designed classiﬁers directly. Further, these...
On The Complexity Of Grobner Basis And Border Basis Detection - Prabhanjan, V A
The theory of Grobner bases has garnered the interests of a large number of researchers in computational algebra due to its applications not only in mathematics but also in areas like control systems, robotics, cryptography to name a few. It is well known that the computation of Grobner bases takes time doubly exponential in the number of indeterminates rendering it impractical in all but a few places.The current known algorithms for Grobner bases depend on the term order over which Grobner bases is computed. In this thesis, we study computational complexity of some problems in computational ideal theory. We also...
Petri Net Model Based Energy Optimization Of Programs Using Dynamic Voltage And Frequency Scaling - Arun, R
High power dissipation and on-chip temperature limit performance and affect reliability in modern microprocessors. For servers and data centers, they determine the cooling cost, whereas for handheld and mobile systems, they limit the continuous usage of these systems. For mobile systems, energy consumption affects the battery life. It can not be ignored for desktop and server systems as well, as the contribution of energy continues to go up in organizations’ budgets, influencing strategic decisions, and its implications on the environment are getting appreciated. Intelligent trade-offs involving these quantities are critical to meet the performance demands of many modern applications.
On A Cubic Sieve Congruence Related To The Discrete Logarithm Problem - Vivek, Srinivas V
There has been a rapid increase interest in computational number theory ever since the invention of public-key cryptography. Various attempts to solve the underlying hard problems behind public-key cryptosystems has led to interesting problems in computational number theory. One such problem, called the cubic sieve congruence problem, arises in the context of the cubic sieve method for solving the discrete logarithm problem in prime fields.
The cubic sieve method requires a nontrivial solution to the Cubic Sieve Congruence (CSC)x3 y2z (mod p), where p is a given prime. A nontrivial solution must satisfy
x3 y2z (mod p), x3 ≠ y2z, 1≤...
Compiler Transformations For Improving The Performance Of Software Transactional Memory - Mannarswamy, Sandya S
Expressing synchronization using traditional lock based primitives has been found to be both error-prone and restrictive. Hence there has been considerable research work to develop scalable and programmer-friendly alternatives to lock-based synchronization. Atomic sections have been proposed as a programming idiom for expressing synchronization at a higher-level of abstraction than locks.
One way of supporting atomic sections in software is to rely on an underlying Software Transactional Memory (STM) implementation. While STM offers the promise of being a programming paradigm which is less error-prone and more programmer friendly compared to traditional lock-based synchronization, it also needs to be competitive in...