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

Videos are expected to be a primary contributor to an anticipated massive surge in mobile network data. Caching the videos within the mobile network can significantly reduce the network load and Operational Expenditure (OPEX) for mobile network operators. Multi-access Edge Computing (MEC) can enable the video caching by providing processing and storage capabilities within the network. However, content providers usually employ Dynamic Adaptive Streaming over HTTP (DASH) for video streaming, which contains multiple bit-rate representations of videos. Constrained by its capacity, MEC can not cache all representations of popular videos. Video transcoding mitigates this issue to a certain extent by converting the higher available video bit-rate to a requested lower one; but, it can quickly exhaust the available edge processing power by transcoding a large number of videos in parallel. Therefore, caching appropriate video bit-rates that can serve the maximum number of users in the network is a non-trivial problem. To resolve this problem and to efficiently utilize the resources (processing and storage) at the network edge, we took a non-traditional approach for video caching that utilizes the network information provided by MEC's Radio Network Information (RNI) Application Program Interface (API). In particular, RNI API provides Radio Access Network (RAN) status information that can be employed to estimate the probability distribution of requested video qualities. In this work, we formulate the video caching problem as an Integer Linear Programming (ILP) for the hit-rate maximization. Since the optimization problem requires the knowledge of all future requests, it obviously cannot be used in real-time. Therefore, we develop a RAN-aware Adaptive VidEo cachiNg (RAVEN) method that uses network information to make an informed decision for video bit-rate selection in video caching coupled with transcoding and maximizes the number of served users form the network edge. Simulation results demonstrate that the RAVEN significantly outperforms state-of-the-art algorithms in the domain and performs closer to the optimal solution. © 2020 Elsevier Ltd

World University root node

Fulltext

Journal of Network and Computer Applications

RAN-aware adaptive video caching in multi-access edge computing networks

To meet the rising data-offloading demands, IEEE 802.11-based WiFi networks have undergone consistent densification. The unlicensed spectrum has also been harnessed through LTE-WiFi coexistence. However, in dense and ultradense networks (DNs/UDNs), the network capacity is even more adversely impacted by the endemic interference. Yet, the precise nature of Capacity Interference Relationship (CIR) in DNs/UDNs and LTE-WiFi coexistence remains to be studied. Densification also exacerbates the challenges to network optimization. The conventional approaches to simplify the complex SINR-Capacity constraints lead to high convergence times in DN/UDN optimization. We investigate the CIR in dense and ultra-dense WiFi (IEEE 802. 11a) and LTE-WiFi (LTULAA) networks through real-time experiments. We then subject the empirical data to linear and polynomial regression to determine the nature of CIR and demonstrate that strong linear correlations may exist. We also study the impact of predictor variables, topology, and radio access technology on CIR. Most importantly, we propose CIRNO, a CIR-inspired network optimization approach, wherein the empirically determined CIR equation replaces the theoretically assumed SINR-Capacity constraints in optimization formulations. We evaluate CIRNO by implementing three recent works on optimization. We demonstrate the relevance of CIR and CIRNO in DNs/UDNs through a significant reduction in convergence times (by over 50%) while maintaining high accuracy (over 95%). To the best of our knowledge, this is the first work to statistically analyze CIR in DNs/UDNs and LTE-WiFi heterogeneous networks (HetNets) and to use CIR regression equations in network optimization. © 2020 IEEE.

IEEE Wireless Communications and Networking Conference, WCNC

CIRNO: Leveraging Capacity Interference Relationship for Dense Networks optimization

Intersections are one of the main sources of congestion and hence, it is important to understand traffic behavior at intersections. Particularly, in developing countries with high vehicle density, mixed traffic type, and lane-less driving behavior, it is difficult to distinguish between congested and normal traffic behavior. In this work, we propose a way to understand the traffic state of smaller spatial regions at intersections using traffic graphs. The way these traffic graphs evolve over time reveals different traffic states - a) a congestion is forming (clumping), the congestion is dispersing (unclumping), or c) the traffic is flowing normally (neutral). We train a spatio-temporal deep network to identify these changes. Also, we introduce a large dataset called EyeonTraffic (EoT) containing 3 hours of aerial videos collected at 3 busy intersections in Ahmedabad, India. Our experiments on the EoT dataset show that the traffic graphs can help in correctly identifying congestion-prone behavior in different spatial regions of an intersection. © 2020 IEEE.

2020 IEEE 23rd International Conference on Intelligent Transportation Systems, ITSC 2020

Defining Traffic States using Spatio-temporal Traffic Graphs

We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2O(√k)(n + m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs cannot be solved in time 2o(√k)(n + m)O(1) [de Berg et al., STOC 2018], hence our algorithm is optimal. Besides the 2O(√k)(n + m)O(1)-time algorithm for the (arguably) much simpler Vertex Cover problem by de Berg et al. [STOC 2018] (which easily follows from the existence of a 2k-vertex kernel for the problem), this is the only known ETH-optimal fixed-parameter tractable algorithm on UDGs. Previously, Long Path and Long Cycle on unit disk graphs were only known to be solvable in time 2O(√k log k)(n + m). This algorithm involved the introduction of a new type of a tree decomposition, entailing the design of a very tedious dynamic programming procedure. Our algorithm is substantially simpler: we completely avoid the use of this new type of tree decomposition. Instead, we use a marking procedure to reduce the problem to (a weighted version of) itself on a standard tree decomposition of width O(√k). © Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi; licensed under Creative Commons License CC-BY 36th International Symposium on Computational Geometry (SoCG 2020).

Leibniz International Proceedings in Informatics, LIPIcs

Eth-tight algorithms for long path and cycle on unit disk graphs

Spoofing the identity of a WiFi access point (AP) is trivial. Consequently, an adversary can impersonate the legitimate AP (LAP) by mimicking its network name (SSID) and MAC address (BSSID). This fake AP is called the evil twin. An evil twin can perform multiple attacks such as man-in-the-middle (MITM) attack between the LAP and a wireless client as well as service blocking of LAP. Existing solutions rely on the collection and calculation of information with the AP and/or client for finding evidence of evil twins in the WiFi network. Some of them require additional hardware to acquire further information that cannot be provided by the AP/client. In this paper, we propose 'EvilScout,' an evil twin detection and mitigation framework that utilizes the information of the IP-prefix distribution by the LAP. EvilScout exploits the SDN potential for detection of an evil twin without the need of any additional hardware or modifications at the AP or client. Additionally, the information that becomes available at the SDN controller enables simplified and more accurate evil twin detection. This paper presents the implementation of EvilScout over a real SDN WiFi testbed with an actual evil twin. We verify the successful detection of the evil twin with high accuracy and low processing cost at the SDN WiFi. We perform a rigorous analysis of the evil twin in different WiFi setups and discover a new 'AP Service Blocking' attack by the evil twin adversary in the WPA2 protected WiFi for the first time. © 2004-2012 IEEE.

IEEE Transactions on Network and Service Management

EvilScout: Detection and Mitigation of Evil Twin Attack in SDN Enabled WiFi

Despite advances in deep learning and facial recognition techniques, the problem of fault-intolerant facial recognition remains challenging. With the current state of progress in the field of automatic face recognition and the in-feasibility of fully manual recognition, the situation calls for human-machine collaborative methods. We design a system that uses machine predictions for a given face to generate queries that are answered by human experts to provide the system with the information required to predict the identity of the face correctly. We use a Markov Decision Process for which we devise an appropriate query structure and a reward structure to generate these queries in a budget or accuracy-constrained setting. Finally, as we do not know the capabilities of the human experts involved, we model each human as a bandit and adopt a multi-armed bandit approach with consensus queries to efficiently estimate their individual accuracies, enabling us to maximize the accuracy of our system. Through careful analysis and experimentation on real-world data-sets using humans, we show that our system outperforms methods that exploit only machine intelligence, simultaneously being highly cost-efficient as compared to fully manual methods. In summary, our system uses human-machine collaboration for face recognition problem more intelligently and efficiently. © 2020 Association for Computing Machinery.

ACM International Conference Proceeding Series

Human-machine collaboration for face recognition

In a reconfiguration version of a decision problem Q the input is an instance of Q and two feasible solutions S and T. The objective is to determine whether there exists a step-by-step transformation between S and T such that all intermediate steps also constitute feasible solutions. In this work, we study the parameterized complexity of the Connected Dominating Set Reconfiguration problem (CDS-R). It was shown in previous work that the Dominating Set Reconfiguration problem (DS-R) parameterized by k, the maximum allowed size of a dominating set in a reconfiguration sequence, is fixed-parameter tractable on all graphs that exclude a biclique Kd,d as a subgraph, for some constant d ≥ 1. We show that the additional connectivity constraint makes the problem much harder, namely, that CDS-R is W[1]-hard parameterized by k + `, the maximum allowed size of a dominating set plus the length of the reconfiguration sequence, already on 5-degenerate graphs. On the positive side, we show that CDS-R parameterized by k is fixed-parameter tractable, and in fact admits a polynomial kernel on planar graphs. © Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz;

On the parameterized complexity of reconfiguration of connected dominating sets

In the Topological Minor Deletion (TM-Deletion) problem, the input consists of an undirected graph G, a family of undirected graphs F and an integer k. The task is to determine whether G contains a set of vertices S of size at most k, such that the graph Gg- S obtained from G by removing the vertices of S, contains no graph from F as a topological minor. We give an algorithm forTM-Deletion with running time f(hg,k)· |V(G)|4. Here hg is the maximum size of a graph in F and f is a computable function of hg and k. This is the first fixed parameter tractable algorithm (FPT) for the problem. In fact, even for the restricted case of planar inputs the first FPT algorithm was found only recently by Golovach et al. [SODA 2020]. For this case we improve upon the algorithm of Golovach et al. [SODA 2020] by designing an FPT algorithm with explicit dependence on k and hg. © 2020 ACM.

Proceedings of the Annual ACM Symposium on Theory of Computing

Hitting topological minors is FPT

Genomic selection (GS) is a popular breeding method that uses genome-wide markers to predict plant phenotypes. Empirical studies and simulations have shown that GS can greatly accelerate the breeding cycle, beyond what is possible with traditional quantitative trait locus (QTL) approaches. GS is a regression problem, where one often uses SNPs to predict the phenotypes. Since the SNP data are extremely high-dimensional, of the order of 100 K dimensions, it is difficult to make accurate phenotypic predictions. Moreover, finding the optimal prediction model is computationally very costly. Out of thousands of SNPs, usually only a few influence a particular phenotypic trait. We first of all show how ensemble-based regression techniques give better prediction accuracy compared to traditional regression methods, which have been used in existing papers. We then further improve the prediction accuracy by using an ensemble of feature selection and feature extraction techniques, which also reduces the time to compute the regression model parameters. We predict three traits: grain yield, time to 50% flowering and plant height for which the existing methods give an accuracy of 0.304, 0.627 and 0.341, respectively. Our proposed regression model gives an accuracy of 0.330, 0.674 and 0.458 for these traits. Additionally, we also propose a computationally efficient regression model that reduces the computation time by as much as 90% and gives an accuracy of 0.342, 0.580 and 0.411, respectively. © 2020, Korean Society of Crop Science (KSCS).

Journal of Crop Science and Biotechnology

Efficient genomic selection using ensemble learning and ensemble feature reduction

The task of generating incorrect options for multiple-choice questions is termed as distractor generation problem. The task requires high cognitive skills and is extremely challenging to automate. Existing neural approaches for the task leverage encoder-decoder architecture to generate long distractors. However, in this process two critical points are ignored - firstly, many methods use Jaccard similarity over a pool of candidate distractors to sample the distractors. This often makes the generated distractors too obvious or not relevant to the question context. Secondly, some approaches did not consider the answer in the model, which caused the generated distractors to be either answer-revealing or semantically equivalent to the answer. In this paper, we propose a novel Hierarchical Multi-Decoder Network (HMD-Net) consisting of one encoder and three decoders, where each decoder generates a single distractor. To overcome the first problem mentioned above, we include multiple decoders with a dis-similarity loss in the loss function. To address the second problem, we exploit richer interaction between the article, question, and answer with a SoftSel operation and a Gated Mechanism. This enables the generation of distractors that are in context with questions but semantically not equivalent to the answers. The proposed model outperformed all the previous approaches significantly in both automatic and manual evaluations. In addition, we also consider linguistic features and BERT contextual embedding with our base model which further push the model performance. © 2020 ACM.

International Conference on Information and Knowledge Management, Proceedings

Learning to Distract: A Hierarchical Multi-Decoder Network for Automated Generation of Long Distractors for Multiple-Choice Questions for Reading Comprehension