Department of Computer Science and Engineering

Indian Institute of Technology Hyderabad (IITH) is a premier institute of science and technology established in 2008. IITH has been consistently ranked in the&nbsp;<a href="https://iith.ac.in/reports/" rel="noopener noreferrer">top 10 institutes</a>&nbsp;in India for Engineering&nbsp;<a href="https://www.nirfindia.org/2021/EngineeringRanking.html" rel="noopener noreferrer" target="_blank">according to NIRF</a>&nbsp;making it one of the most coveted schools for science and technology in the country.

IITH offers&nbsp;<a href="https://iith.ac.in/academics/under-graduate/">undergraduate programs</a>&nbsp;in all the classical engineering disciplines, applied sciences, design, as well as several modern interdisciplinary areas. Students are given a flexibility to explore a broad set of areas, and potentially pursue a minor or double major in a discipline that is not their own. Students who wish to seek a deeper understanding of their own discipline are strongly encouraged to get involved in cutting-edge research with the help of a faculty to mentor them, and earn an Honors in their own field.

The very foundation of IIT Hyderabad is based on&nbsp;<a href="https://iith.ac.in/research/">research and innovation</a>. The vibrant research culture is evident from the number of patents and publications that IITH produces consistently every year. IITH offers&nbsp;<a href="https://iith.ac.in/academics/programmes-offered/">graduate programs</a>&nbsp;at both a masters, and a doctoral level, in several diverse areas. There are separate programs for technology, design, science, and liberal arts. The&nbsp;<a href="https://iith.ac.in/academics/post-graduate/">MTech program</a>&nbsp;is offered in various modes and durations to cater to the ever-growing need of postgraduate level professionals in the country.

IITH encourages and supports&nbsp;<a href="https://iic-iith.netlify.app/index.html" rel="noopener noreferrer" target="_blank">innovation and entrepreneurship</a>&nbsp;at every stage. The minor program in entrepreneurship is open to all students of IITH, and many of the courses are offered by industrialists who are entrepreneurs themselves. There are various&nbsp;<a href="https://iith.ac.in/research/centres-incubators/">innovation centers and incubators</a>&nbsp;that promote entrepreneurship and help mentor young innovators. IITH has been very successful in building tie-ups with leading academic institutions around the globe.

IITH enjoys a very special relationship with Japanese universities and industries that goes beyond academic and research collaborations. In fact, some of the iconic buildings in IITH campus will carry the signature of Japanese architecture.

IITH creates a unique holistic ecosystem for education that offers interactive learning, a very flexible academic structure, cutting-edge research, strong industry collaboration, and entrepreneurship. This is an environment which enables students and faculty to translate their dreams into realities.

IIT Hyderabad

Active learning techniques have gained popularity to reduce human effort in labeling data instances for inducing a classifier. When faced with large amounts of unlabeled data, such algorithms automatically identify the exemplar and representative instances to be selected for manual annotation. More recently, there have been attempts toward a batch mode form of active learning, where a batch of data points is simultaneously selected from an unlabeled set. Real-world applications require adaptive approaches for batch selection in active learning, depending on the complexity of the data stream in question. However, the existing work in this field has primarily focused on static or heuristic batch size selection. In this paper, we propose two novel optimization-based frameworks for adaptive batch mode active learning (BMAL), where the batch size as well as the selection criteria are combined in a single formulation. We exploit gradient-descent-based optimization strategies as well as properties of submodular functions to derive the adaptive BMAL algorithms. The solution procedures have the same computational complexity as existing state-of-the-art static BMAL techniques. Our empirical results on the widely used VidTIMIT and the mobile biometric (MOBIO) data sets portray the efficacy of the proposed frameworks and also certify the potential of these approaches in being used for real-world biometric recognition applications. © 2014 IEEE.

World University root node

IEEE Transactions on Neural Networks and Learning Systems

Adaptive Batch Mode Active Learning

Active learning techniques have gained popularity to reduce human effort in labeling data instances for inducing a classifier. When faced with large amounts of unlabeled data, such algorithms automatically identify the exemplar instances for manual annotation. More recently, there have been attempts towards a batch mode form of active learning, where a batch of data points is simultaneously selected from an unlabeled set. In this paper, we propose two novel batch mode active learning (BMAL) algorithms: BatchRank and BatchRand. We first formulate the batch selection task as an NP-hard optimization problem; we then propose two convex relaxations, one based on linear programming and the other based on semi-definite programming to solve the batch selection problem. Finally, a deterministic bound is derived on the solution quality for the first relaxation and a probabilistic bound for the second. To the best of our knowledge, this is the first research effort to derive mathematical guarantees on the solution quality of the BMAL problem. Our extensive empirical studies on $15$ binary, multi-class and multi-label challenging datasets corroborate that the proposed algorithms perform at par with the state-of-the-art techniques, deliver high quality solutions and are robust to real-world issues like label noise and class imbalance. © 1979-2012 IEEE.

IEEE Transactions on Pattern Analysis and Machine Intelligence

Active Batch Selection via Convex Relaxations with Guaranteed Solution Bounds

For a graph H, the H-free Edge Deletion problem asks whether there exist at most k edges whose deletion from the input graph G results in a graph without any induced copy of H. We prove that H-free Edge Deletion is NP-complete if H is a graph with at least two edges and H has a component with maximum number of vertices which is a tree or a regular graph. Furthermore, we obtain that these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time 2o(k)⋅|G|O(1), unless Exponential Time Hypothesis fails. © Springer International Publishing Switzerland 2015.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Parameterized lower bound and np-completeness of some h-free edge deletion problems

Classification of medical data is one of the most challenging pattern recognition problems. As stated in literature a single classifier is unable to solve all medical image classification problems due to high sensitivity to noise and other imperfections like data imbalance. So, several individual classifiers have been studied to solve the different types of classification problems arising in medical datasets but all have proven to be useful on some specific datasets. Hence, in this paper, we propose a generic multi-level classification approach for medical datasets using sparsity based dictionary learning and support vector machine approaches. The proposed technique demonstrates the following advantages: 1) gives better performance of classification accuracy over all datasets 2) solves imbalanced data problems 3) needs no fusion and ensemble methods in multi-level classification. The results presented on the 5 standard UCI medical datasets demonstrate that the efficacy of the proposed multi-level classification technique. © 2015 IEEE.

Department of Electrical Engineering

2015 17th International Conference on E-Health Networking, Application and Services, HealthCom 2015

Multi-level classification: A generic classification method for medical datasets

Feature descriptors involved in video processing are generally high dimensional in nature. Even though the extracted features are high dimensional, many a times the task at hand depends only on a small subset of these features. For example, if two actions like running and walking have to be identified, extracting features related to the leg movement of the person is enough. Since, this subset is not known apriori, we tend to use all the features, irrespective of the complexity of the task at hand. Selecting task-aware features may not only improve the efficiency but also the accuracy of the system. In this work, we propose a supervised approach for task-aware selection of features using Deep Neural Networks (DNN) in the context of action recognition. The activation potentials contributed by each of the individual input dimensions at the first hidden layer are used for selecting the most appropriate features. The selected features are found to give better classification performance than the original high-dimensional features. It is also shown that the classification performance of the proposed feature selection technique is superior to the low-dimensional representation obtained by principal component analysis (PCA). © 2015 IEEE.

Proceedings of the International Joint Conference on Neural Networks

Feature selection using Deep Neural Networks

In this work, we study the well-known r-DIMENSIONAL k-MATCHING ((r, k)-DM), and r-SET k-PACKING ((r, k)-SP) problems. Given a universe U := U1 ⋯ Ur and an r-uniform family F ⊆ U1 × ⋯ × Ur, the (r, k)-DM problem asks if F admits a collection of k mutually disjoint sets. Given a universe U and an r-uniform family F ⊆ 2U, the (r,k)SP problem asks if F admits a collection of k mutually disjoint sets. We employ techniques based on dynamic programming and representative families. This leads to a deterministic algorithm with running time O(2.851(r-1)k. |F|. n log2 n-log W) for the weighted version of (r, k)-DM, where W is the maximum weight in the input, and a deterministic algorithm with running time O(2.851(r-0.5501)k · |F| · nlog2 n · logW) for the weighted version of (r, k)SP. Thus, we significantly improve the previous best known deterministic running times for (r, k)-DM and (r, k)SP and the previous best known running times for their weighted versions. We rely on structural properties of (r, k)-DM and (r, k)SP to develop algorithms that are faster than those that can be obtained by a standard use of representative sets. Incorporating the principles of iterative expansion, we obtain a better algorithm for (3,k)-DM, running in time O(2.0043k · |F| · nlog2 n). We believe that this algorithm demonstrates an interesting application of representative families in conjunction with more traditional techniques. Furthermore, we present kernels of size O(err(k - 1)r log W) for the weighted versions of (r, k)-DM and (r, k)-SP, improving the previous best known kernels of size O(r!r(k-1)r logW) for these problems. © 2015 Society for Industrial and Applied Mathematics.

SIAM Journal on Discrete Mathematics

Deterministic algorithms for Mat ching and packing problems based on representative sets

For fixed integers r, ℓ ≥ 0, a graph G is called an (r, ℓ)-graph if the vertex set V (G) can be partitioned into r independent sets and ' cliques. This brings us to the following natural parameterized questions: Vertex (r, ℓ)-Partization and Edge (r, ℓ)-Partization. An input to these problems consist of a graph G and a positive integer k and the objective is to decide whether there exists a set S ⊆ V (G) (S ⊆ E(G)) such that the deletion of S from G results in an (r, ℓ)-graph. These problems generalize well studied problems such as Odd Cycle Transversal, Edge Odd Cycle Transversal, Split Vertex Deletion and Split Edge Deletion. We do not hope to get parameterized algorithms for either Vertex (r, ℓ)-Partization or Edge (r, ℓ)- Partization when either of r or ℓ is at least 3 as the recognition problem itself is NP-complete. This leaves the case of r, ℓ ∈ {1, 2}. We almost complete the parameterized complexity dichotomy for these problems by obtaining the following results: 1. We show that Vertex (r, ℓ)-Partization is fixed parameter tractable (FPT) for r, ℓ ∈ {1, 2}. Then we design an O(√log n)-factor approximation algorithms for these problems. These approximation algorithms are then utilized to design polynomial sized randomized Turing kernels for these problems. 2. Edge (r, ℓ)-Partization is FPT when (r, ℓ) ∈ {(1, 2), (2, 1)}. However, the parameterized complexity of Edge (2, 2)-Partization remains open. For our approximation algorithms and thus for Turing kernels we use an interesting finite forbidden induced graph characterization, for a class of graphs known as (r, ℓ)-split graphs, properly containing the class of (r, ℓ)-graphs. This approach to obtain approximation algorithms could be of an independent interest. © Sudeshna Kolay and Fahad Panolan;.

Leibniz International Proceedings in Informatics, LIPIcs

Parameterized algorithms for deletion to (r, ℓ)-graphs

In the Steiner tree problem, we are given as input a connected n-vertex graph with edge weights in {1, 2,…, W}, and a subset of k terminal vertices. Our task is to compute a minimum-weight tree that contains all the terminals. We give an algorithm for this problem with running time O(7. 97k ·n4 · logW) using O(n3 · lognW · log k) space. This is the first single-exponential time, polynomial-space FPT algorithm for the weighted Steiner Tree problem. © Springer-Verlag Berlin Heidelberg 2015.

Parameterized single-exponential time polynomial space algorithm for steiner tree

The non-uniform distribution of memory accesses of todays applications affect the performance of cache memories. Due to such non-uniform accesses some sets of large sized caches are used heavily while some other sets are used lightly. This paper presents a technique WS-DAM, to dynamically increase the associativity of the heavily used sets without increasing the cache size. The heavily used sets can use the idle ways of the lightly used sets to distribute the load. A limited number of ways from every lightly used set are reserved for the heavily used sets. To search a block in a heavily used set, both: the set and the entire reserve area is searched. To reduce the cost of searching the entire reserve storage an additional tag-array is used. During execution the sets are re-categorized at intervals. The proposed technique needs much lesser storage, area and power overhead as compared to the other similar techniques. It improves both miss rate and CPI by 14.46% and 6.63% respectively as compared to an existing technique called V-Way. WS-DAM is also compared with another existing proposal called CMP-VR and it improves the performance by 9% and 4.20% in terms of miss-rate and CPI respectively. Copyright 2015 ACM.

Proceedings of the ACM Symposium on Applied Computing

Dynamic associativity management using utility based way-sharing

Most of the chip-multiprocessors share a large sized last level cache(LLC) which is divided into multiple banks in NUCA based architectures. Recent study on LLC power consumption indicates that, LLC consumes principal amount of chip power. The LLC power consumption can be divided into two major parts: dynamic power and static power. Techniques have been proposed to reduce static power by powering off some less utilized cache portions. But, powering off some cache portion can degrade the system performance. In this paper, we reduce the cache power consumption by shutting down some cache ways of less utilized cache sets and then apply victim retention(VR) technique in the remaining portion to reduce cache misses. Experimental analysis shows 35% reduction in static power and 11.31% reduction in EDP, on an average for a 2MB LLC with negligible change in performance. © 2015 IEEE.