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

We study a variant of the folklore Cops and Robbers (also known as pursuit evasion) problem on graphs. In this variant, there are different specializations of cops and a minimum number of each specialization are necessary to catch a robber. To the best of our knowledge, this variant has not been investigated so far. We believe that this problem will find relevance in several domains like biological systems and epidemic response strategies. We seek to compare the ease of catching robbers executing random walks on various graphs, especially complex networks. We use Statistical Model Checking for the analysis. In this initial work, we report experiments that yield interesting results. For example, we show empirically that it is easier to catch robbers on the Barabási-Albert model, than on the Erdős-Rényi model. © 2019, Springer Nature Switzerland AG.

World University root node

Studies in Computational Intelligence

Specialist Cops Catching Robbers on Complex Networks

Composing together the individual atomic methods of concurrent data-structures (cds) pose multiple design and consistency challenges. In this context composition provided by transactions in software transaction memory (STM) can be handy. However, most of the STMs offer read/write primitives to access shared cds. These read/write primitives result in unnecessary aborts. Instead, semantically rich higher-level methods of the underlying cds like lookup, insert or delete (in case of hash-table or lists) aid in ignoring unimportant lower level read/write conflicts and allow better concurrency. In this paper, we adapt transaction tree model in databases to propose OSTM which enables efficient composition in cds. We extend the traditional notion of conflicts and legality to higher level methods of cds using STMs and lay down detailed correctness proof to show that it is co-opaque. We implement OSTM with concurrent closed addressed hash-table (HT-OSTM) and list (list-OSTM) which exports the higher-level operations as transaction interface. In our experiments with varying workloads and randomly generated transaction operations, HT-OSTM shows speedup of 3 to 6 times and w.r.t aborts HT-OSTM is 3 to 7 times better than ESTM and read/write based STM, respectively. Where as, list-OSTM outperforms state of the art lock-free transactional list, NOrec STM list and boosted list by 30% to 80% across all workloads and scenarios. Further, list-OSTM incurred negligible aborts in comparison to other techniques considered in the paper. © Springer Nature Switzerland AG 2019.

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

Efficient means of achieving composability using object based semantics in transactional memory systems

Tags play a crucial role in CQA sites by facilitating organization, indexing and categorization of the entire post in a few words. The choice of tags determines the audience that is elicited upon to seek a response for any particular post. This could either lead to receiving an accurate response for the question or result in receiving no answers. The choice of tags, thus, directly determines the quality of the post as well as to a large extent the success of the CQA site itself. In this paper, we a present a novel approach to evaluate the choice of tags in any post. We perform tag network analysis to find relationship between tags. We then find the anomalous combination of tags by performing anomaly detection. We demonstrate the robustness of our approach by showing high AUC, in the range of 0.95 to 0.98, on four datasets from Stack Exchange, namely Ask Ubuntu, Server Fault, Super User and Software Engineering. © Springer Nature Switzerland AG 2019.

Evaluating the choice of tags in CQA sites

A fixed dimensional representation for action clips of varying lengths has been proposed in the literature using aggregation models like bag-of-words and Fisher vector. These representations are high dimensional and require classification techniques for action recognition. In this paper, we propose a framework for unsupervised extraction of a discriminative low-dimensional representation called action-vector. To start with, local spatio-temporal features are utilized to capture the action attributes implicitly in a large Gaussian mixture model called the universal attribute model (UAM). To enhance the contribution of the significant attributes in each action clip, a maximum aposteriori adaptation of the UAM means is performed for each clip. This results in a concatenated mean vector called super action vector (SAV) for each action clip. However, the SAV is still high dimensional because of the presence of redundant attributes. Hence, we employ factor analysis to represent every SAV only in terms of the few important attributes contributing to the action clip. This leads to a low-dimensional representation called action-vector. This entire procedure requires no class labels and produces action-vectors that are distinct representations of each action irrespective of the inter-actor variability encountered in unconstrained videos. An evaluation on trimmed action datasets UCF101 and HMDB51 demonstrates the efficacy of action-vectors for action classification over state-of-the-art techniques. Moreover, we also show that action-vectors can adequately represent untrimmed videos from the THUMOS14 dataset and produce classification results comparable to existing techniques. © 1999-2012 IEEE.

Department of Electrical Engineering

IEEE Transactions on Multimedia

Unsupervised Universal Attribute Modeling for Action Recognition

We address the challenge of high speed autonomous navigation of micro aerial vehicles (MAVs) using DNNs in GPS-denied environments with limited computational resources; specifically, we use the ODROID XU4 and the Raspberry Pi 3. The high computation costs of using DNNs for inference, particularly in the absence of powerful GPUs, necessitates negotiating a tradeoff between accuracy and inference. We address this tradeoff by employing sparsified neural networks. To obtain such architectures, we propose a novel algorithm to find sparse “sub networks” of existing pre trained models. Contrary to existing pruning-only strategies, our proposal includes a novel exploration step that efficiently searches for a different, but identically sparse, architecture with better generalization abilities. We derive learning theoretic bounds that reinforce our empirical findings that the optimized network achieves comparable generalization to the original network. We show that using our algorithm it is possible to discover models which, on average, have upto 19x fewer parameters than those obtained using existing state of the art pruning methods on autonomous navigation datasets, and achieve upto 6x improvements on inference time compared to existing state of the art shallow models on the ODROID XU4 and Raspberry Pi 3. Last, we demonstrate that our sparsified models can complete autonomous navigation missions with speeds upto 4 m/s using the ODROID XU4, which existing state of the art methods fail to do. © 2019, Springer Nature Switzerland AG.

Optimizing DNN Architectures for High Speed Autonomous Navigation in GPS Denied Environments on Edge Devices

In predictive tasks like classification, Information Gain (IG) based Decision Tree is very popularly used. However, IG method has some inherent problems like its preference towards choosing attributes with higher number of distinct values as the splitting attribute in case of nominal attributes and another problem is associated with imbalanced datasets. Most of the real-world datasets have many nominal attributes, and those nominal attributes may have many number of distinct values. In this paper, we have tried to point out these characteristics of the datasets while discussing the performance of our proposed approach. Our approach is a variant of the traditional Decision Tree model and uses a new technique called Dispersion_Ratio, a modification of existing Correlation Ratio (CR) method. The whole approach is divided into two phases - firstly, the dataset is discretised using a discretization module and secondly, the preprocessed dataset is used to build a Dispersion Ratio based Decision Tree model. The proposed method does not prefer the attributes with many unique values and indifferent about class distribution. It performs better than previously proposed CR based Decision Tree (CRDT) Model since an efficient discretization module has been added with it. We have evaluated the performance of our approach on some benchmark datasets from various domains to demonstrate the effectiveness of the proposed technique and also compared our model with Information Gain, Gain Ratio and Gini Index based models. Result shows that the proposed model outperforms other models in majority of the cases that we have considered in our experiment. © 2018 Elsevier Ltd

Expert Systems with Applications

Dispersion Ratio based Decision Tree Model for Classification

In this paper, we introduce Context-aware Adaptive Embedded Systems (CAES) and illustrate the complexity of early design space exploration (DSE) process using examples of two real systems that are being implemented in our group. Next, we give an overview of the proposed approach and present some preliminary results. © 2019 Association for Computing Machinery.

Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis Companion, CODES/ISSS 2019

Work-in-progress: A case for design space exploration of context-aware adaptive embedded systems

Independent mobility of visually impaired people is key to making an inclusive society for them. Unstructured infrastructure in developing countries pose significant challenges in developing aids to address the mobility problem of visually impaired. Most of the assistive devices available internationally assume a structured and controlled environment severely restricting the applicability of such devices. In this paper, we assess the ability of state-of-the-art assistive devices for addressing the independent outdoor mobility needs of the visually impaired in an unstructured environment. We have created realistic datasets for various scenarios and evaluate deep neural networks for object detection on these datasets. We also present a portable prototype for the task. Further, we have also developed a cloud based solution to address the mobility requirements. We compare the local device based and cloud based solutions in terms of accuracy, latency, and energy. We present and discuss results from these two implementations that can provide insights for an effective solution. The results and insights open up novel research problems for embedded systems. © 2019 IEEE.

Proceedings - 32nd International Conference on VLSI Design, VLSID 2019 - Held concurrently with 18th International Conference on Embedded Systems, ES 2019

Mavi: Mobility assistant for visually impaired with optional use of local and cloud resources

Graph partitioning problems are a central topic of study in algorithms and complexity theory. Edge expansion and vertex expansion, two popular graph partitioning objectives, seek a 2-partition of the vertex set of the graph that minimizes the considered objective. However, for many natural applications, one might require a graph to be partitioned into k parts, for some k &gt; 2. For a k-partition S1,..., Sk of the vertex set of a graph G = (V, E), the k-way edge expansion (resp. vertex expansion) of {S1,..., Sk} is defined as maxi∈[k] Φ(Si), and the balanced k-way edge expansion (resp. vertex expansion) of G is defined as min {S1,...,Sk}∈Pk max i∈[k] Φ(Si) , where Pk is the set of all balanced k-partitions of V (i.e each part of a k-partition in Pk should have cardinality |V |/k), and Φ(S) denotes the edge expansion (resp. vertex expansion) of S ⊂ V. We study a natural planted model for graphs where the vertex set of a graph has a k-partition S1,..., Sk such that the graph induced on each Si has large expansion, but each Si has small edge expansion (resp. vertex expansion) in the graph. We give bi-criteria approximation algorithms for computing the balanced k-way edge expansion (resp. vertex expansion) of instances in this planted model. © Anand Louis and Rakesh Venkat; licensed under Creative Commons License CC-BY.

Leibniz International Proceedings in Informatics, LIPIcs

Planted models for k-way edge and vertex expansion

Power efficiency is one of the grand challenge problems facing computer architecture in recent years. Driven by the growth towards green computing, it is imperative to design architectures that can provide maximum power savings while incurring minimal overhead on real estate and performance. Towards this we propose a state-preserving mechanism for dynamically configuring DRAM banks based on utilization. We propose a novel mechanism via which it is possible to dynamically power down and power on banks while taking the bank utilization and overall performance into account. Over extensive experimentation using memory intensive applications, we can observe a power savings of up to 12.31% while incurring an average performance loss of 0.82% over baseline executions. © 2019 IEEE.