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

The classic K-Cycle problem asks if a graph G, with vertex-set V(G), has a simple cycle containing all vertices of a given set K⊆ V(G). In terms of colored graphs, it can be rephrased as follows: Given a graph G, a set K⊆ V(G) and an injective coloring c: K→ { 1 , 2 , … , | K| } , decide if G has a simple cycle containing each color in { 1 , 2 , … , | K| } exactly once. Another problem widely known since the introduction of color coding is Colorful Cycle. Given a graph G and a coloring c: V(G) → { 1 , 2 , … , k} for some k∈ N, it asks if G has a simple cycle of length k containing each color in { 1 , 2 , … , k} exactly once. We study a generalization of these problems: Given a graph G, a set K⊆ V(G) , a list-coloring L:K→2{1,2,…,k∗} for some k ∗ ∈ N and a parameter k∈ N, ListK-Cycle asks if one can assign a color to each vertex in K so that G has a simple cycle (of arbitrary length) containing exactly k vertices from K with distinct colors. We design a randomized algorithm for ListK-Cycle running in time 2 k n O ( 1 ) on an n-vertex graph, matching the best known running times of algorithms for both K-Cycle and Colorful Cycle. Moreover, unless the Set Cover Conjecture is false, our algorithm is essentially optimal. We also study a variant of ListK-Cycle that generalizes the classic Hamiltonicity problem, where one specifies the size of a solution. Our results integrate three related algebraic approaches, introduced by Björklund, Husfeldt and Taslaman (SODA’12), Björklund, Kaski and Kowalik (STACS’13), and Björklund (FOCS’10). © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

World University root node

Fulltext

Algorithmica

Parameterized Algorithms for List K-Cycle

An edge Hamiltonian path of a graph is a permutation of its edge set where every pair of consecutive edges have a vertex in common. Unlike the seemingly related problem of finding an Eulerian walk, the edge Hamiltonian path is known to be a NP -hard problem, even on fairly restricted classes of graphs. We introduce a natural optimization variant of the notion of an edge Hamiltonian path, which seeks the longest sequence of distinct edges with the property that every consecutive pair of them has a vertex in common. We call such a sequence of edges an edge-linked path, and study the parameterized complexity of the problem of finding edge-linked paths with at least k edges. We show that the problem is FPT when parameterized by k, and unlikely to admit a polynomial kernel even on connected graphs. On the other hand, we show that the problem admits a Turing kernel of polynomial size. To the best of our knowledge, this is the first problem on general graphs to admit Turing kernels with adaptive oracles (for which a non-adaptive kernel is not known). We also design a single-exponential parameterized algorithm for the problem when parameterized by the treewidth of the input graph. © Springer Nature Switzerland AG 2019.

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

On the parameterized complexity of edge-linked paths

We propose a dimensionality reduction (sketching) algorithm for high dimensional, sparse, binary data. Our proposed algorithm provides a single sketch which simultaneously preserves multiple similarity measures including Hamming distance, Inner product, and Jaccard Similarity [12]. In contrast to the »local projection» strategy used by most of the earlier algorithms [6], [4], [7], our approach exploits sparsity and combines the following two strategies: 1. partitioning the dimensions into several buckets, 2. obtaining »global linear summaries» within those buckets. Our algorithm is faster than the existing state-of-the-art, and it preserves the binary format of the data after the dimensionality reduction, which makes the sketch space efficient. Our algorithm can also be easily adapted in streaming and incremental learning frameworks. We give a rigorous theoretical analysis of the dimensionality reduction bounds and complement it with extensive experiments. Our proposed algorithm is simple and easy to implement in practice. © 2018 IEEE.

Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018

Efficient Dimensionality Reduction for Sparse Binary Data

Recent advancement of the WWW, IOT, social network, e-commerce, etc. have generated a large volume of data. These datasets are mostly represented by high dimensional and sparse datasets. Many fundamental subroutines of common data analytic tasks such as clustering, classification, ranking, nearest neighbour search, etc. scale poorly with the dimension of the dataset. In this work, we address this problem and propose a sketching (alternatively, dimensionality reduction) algorithm - BinSketch (Binary Data Sketch) - for sparse binary datasets. BinSketch preserves the binary version of the dataset after sketching and maintains estimates for multiple similarity measures such as Jaccard, Cosine, Inner-Product similarities, and Hamming distance, on the same sketch. We present a theoretical analysis of our algorithm and complement it with extensive experimentation on several real-world datasets. We compare the performance of our algorithm with the state-of-the-art algorithms on the task of mean-square-error and ranking. Our proposed algorithm offers a comparable accuracy while suggesting a significant speedup in the dimensionality reduction time, with respect to the other candidate algorithms. Our proposal is simple, easy to implement, and therefore can be adopted in practice. © 2019 IEEE.

Proceedings - IEEE International Conference on Data Mining, ICDM

Efficient sketching algorithm for sparse binary data

The problem of tax evasion is as old as taxes itself. Tax evasion causes several problems that affects the growth of a nation. In this paper, we present our work in controlling tax evasion by using big data analytics, Android applications, and information technology. We implemented this work for the commercial taxes department, government of Telangana, India. Here we developed a complete software framework for scrutiny of suspicious accounts. This system detects suspicious dealers using certain sensitive parameters and standardizes the process of scrutiny of accounts. We used sophisticated statistical and machine learning tools to predict suspicious dealers. To increase the compliance levels, we developed a regression model for identifying return defaulters and user-friendly Android applications to assist the officers in collecting the tax. The other aspect we explored is the detection and analysis of a tax evasion mechanism, known as circular trading, using advanced algorithmic and social-network analytic techniques. © 2019, Springer Nature Switzerland AG.

Big Data Analytics for Tax Administration

Vehicle trajectory prediction at intersections is both essential and challenging for autonomous vehicle navigation. This problem is aggravated when the traffic is predominantly composed of smaller vehicles that frequently disobey lane behavior as is the case in many developing countries. Existing macro approaches consider the trajectory prediction problem for lane-based traffic that cannot account when there is a high disparity in vehicle size and driving behavior among different vehicle types. Hence, we propose a vehicle trajectory prediction approach that models the interaction among different types of vehicles with vastly different driving styles. These interactions are encapsulated in the form of a social context embedded in a Generative Adversarial Network (GAN) to predict the trajectory of each vehicle at either a signalized or non-signalized intersection. The GAN model produces the most acceptable future trajectory among many choices that conform to past driving behavior as well as the trajectories of neighboring vehicles. We evaluate the proposed approach on aerial videos of intersections recorded in China where lane discipline is not followed by vehicles. The proposed GAN based approach demonstrates 6.4% relative improvement in predicting trajectories over state-of-the-art. © 2019 IEEE.

2019 IEEE Intelligent Transportation Systems Conference, ITSC 2019

Vehicle Trajectory Prediction at Intersections using Interaction based Generative Adversarial Networks

Many program-analysis based tools require precise points-to/alias information only for some program variables. To meet this requirement efficiently, there have been many works on demand-driven analyses that perform only the work necessary to compute the points-to or alias information on the requested variables (queries). However, these demand-driven analyses can be very expensive when applied on large systems where the number of queries can be significant. Such a blow-up in analysis time is unacceptable in cases where scalability with real-time constraints is crucial; for example, when program analysis tools are plugged into an IDE (Integrated Development Environment). In this paper, we propose schemes to improve the scalability of demand-driven analyses without compromising on precision. Our work is based on novel ideas for eliminating irrelevant and redundant data-flow paths for the given queries. We introduce the idea of batch analysis, which can answer multiple given queries in batch mode. Batch analysis suits the environments with strict time constraints, where the queries come in batch. We present a batch alias analysis framework that can be used to speed up given demand-driven alias analysis. To show the effectiveness of this framework, we use two demand-driven alias analyses (1) the existing best performing demand-driven alias analysis tool for race-detection clients and (2) an optimized version thereof that avoids irrelevant computation. Our evaluations on a simulated data-race client, and on a recent program-understanding tool, show that batch analysis leads to significant performance gains, along with minor gains in precision. © 2019 IEEE.

Proceedings - 2019 34th IEEE/ACM International Conference on Automated Software Engineering, ASE 2019

Batch alias analysis

AllJoyn is an open-source framework which has the potential to be the platform for next-generation proximity centric disaster network (DiNet) applications. However, its development is still in nascent stages, and one of the primary challenges is the design of efficient routing algorithms, which can ensure seamless and uninterrupted communication in an unfavorable environment. In this work, we implement a DiNet prototype using AllJoyn to highlight the challenges of multi-hop routing and propose the concept of extended proximity (e-proximity) in AllJoyn. As a first step towards solving this challenge, we carry out field experiments by implementing an AllJoyn file-transfer application on a trivial DiNet prototype. We then evaluate the performance of the AllJoyn based disaster network and demonstrate that AllJoyn can support robust and reliable DiNet applications. © 2019 Association for Computing Machinery.

ACM International Conference Proceeding Series

Designing infrastructure-less disaster networks by leveraging the alljoyn framework

LTE-Heterogeneous Networks (HetNets) with dense deployment of small cells are expected to effectively meet unprecedented ever increasing data traffic demands and offer improved coverage in indoor environments. However, HetNets are raising major issues to Mobile Network Operators (MNOs) such as complex distributed control plane management and increased energy costs. Hence, MNOs are looking for flexible software defined mobile architectures to reduce their capital expenditure (CAPEX) and operational expenditure (OPEX). In this work, in order to reduce energy costs of the HetNets, we propose an interference and QoS aware cell switch-off strategy (IQ-CSOS) on a software defined LTE Radio Access Network (SD-LTE-RAN) framework. Unlike existing CSOSs, IQ-CSOS investigates both network energy costs and QoS satisfaction of sessions during CSOS decisions. In performance evaluation under various test scenarios, it is found that IQ-CSOS is able to provide 50–80% of network energy savings. Besides, it is able to provide 30% more energy savings compared to existing CSOSs with slight affect on network QoS. © 2018 Elsevier Ltd

Journal of Network and Computer Applications

Interference and QoS aware cell switch-off strategy for software defined LTE HetNets

Vehicle-to-vehicle networks have gained significant interest in recent times from researchers all around the world. V2V/V2I are emerging as an efficient solution for achieving road safety and securely transmitting data from one vehicle to other. However, in such opportunistic environments such as a sparse vehicular network where disruption, dynamic network topology, fast vehicle movement, and environmental conditions are the major concerns, data forwarding is extremely challenging. Traditional ad-hoc routing protocols like Ad hoc On-Demand Distance Vector (AODV) and Dynamic Source Routing (DSR) fail to deliver in such laborious conditions. Routing protocols of Delay/Disruption Tolerant Networks(DTN) exploit the Store-Carry-Forward Mechanism (SCF) strategy in these cases. Taking advantage of temporary connections to disseminate information is the focus of DTN. DTN helps to increase information propagation coverage in sparse areas where there are very few devices. In this paper, we first compare the performance of AllJoyn framework and Direct Delivery protocol in a single-hop scenario and then draw the attention towards a multi-hop scenario by comparing other three routing protocols that use DTN as the underlying paradigm. These protocols are Flooding, Epidemic, and PRoPHET. The performances are evaluated by transmitting the files of size 1, 4, and 10 MB from a static sender to a mobile receiver in the multi-hop scenario. We also develop an Android application that contains the implementation of these routing protocols along with file sharing functionality. From the outcomes of this experiment, it can be said that Epidemic routing protocol performs the best in our considered multi-hop scenario in terms of transfer delay, coverage, and throughput whereas, Direct Delivery routing protocol performs better than AllJoyn in single-hop communication. © 2019 IEEE.