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

Outlier detection is a challenging activity. Several machine learning techniques are proposed in the literature for outlier detection. In this article, we propose a new training approach for bidirectional GAN (BiGAN) to detect outliers. To validate the proposed approach, we train a BiGAN with the proposed training approach to detect taxpayers, who are manipulating their tax returns. For each taxpayer, we derive six correlation parameters and three ratio parameters from tax returns submitted by him/her. We train a BiGAN with the proposed training approach on this nine-dimensional derived ground-truth data set. Next, we generate the latent representation of this data set using the encoder (encode this data set using the encoder) and regenerate this data set using the generator (decode back using the generator) by giving this latent representation as the input. For each taxpayer, compute the cosine similarity between his/her ground-truth data and regenerated data. Taxpayers with lower cosine similarity measures are potential return manipulators. We applied our method to analyze the iron and steel taxpayer's data set provided by the Commercial Taxes Department, Government of Telangana, India. © 2022 IEEE.

World University root node

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

Enhancement to Training of Bidirectional GAN : An Approach to Demystify Tax Fraud

Entanglement swapping is a basic primitive in long distance quantum communications. The stochastic nature of various operations like entanglement generation and BSMs makes the entanglement swapping primitive failure prone. It is difficult to predict whether or not an entanglement swapping operation will succeed within a stipulated time. In this paper, we use Probabilistic Timed Automata (PTA) to model the experiment and analyze it through model checking. We report a proof-of-concept mechanism, opening way for the analysis of large scale quantum networks through formal methods. We also report supporting results on a quantum simulator. © 2022, Springer Nature Switzerland AG.

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

Model Checking for Entanglement Swapping

For Affine Control Programs or Static Control Programs (SCoP), symbolic counting of reuse distances could induce polynomials for each reuse pair. These polynomials along with cache capacity constraints lead to non-Affine (semi-Algebraic) sets; and counting these sets is considered to be a hard problem. The state-of-The-Art methods use various exact enumeration techniques relying on existing cardinality algorithms that can efficiently count affine sets.We propose BullsEye , a novel, scalable, accurate, and problem-size independent approximation framework. It is an analytical cache model for fully associative caches with LRU replacement policy focusing on sampling and linearization of non-Affine stack distance polynomials. First, we propose a simple domain sampling method that can improve the scalability of exact enumeration. Second, we propose linearization techniques relying on Handelman's theorem and Bernstein's representation. To improve the scalability of the Handelman's theorem linearization technique, we propose template (Interval or Octagon) sub-polyhedral approximations.Our methods obtain significant compile-Time improvements with high-Accuracy when compared to HayStack on important polyhedral compilation kernels such as nussinov, cholesky, and adi from PolyBench, and harris, gaussianblur from LLVM-TestSuite. Overall, on PolyBench kernels, our methods show up to 3.31× (geomean) speedup with errors below ≈ 0.08% (geomean) for the octagon sub-polyhedral approximation. © 2022 Association for Computing Machinery.

ACM Transactions on Architecture and Code Optimization

BullsEye : Scalable and Accurate Approximation Framework for Cache Miss Calculation

In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The MATCHING CUT problem is the problem of deciding whether a given graph has a matching cut. Let H be a fixed undirected graph. A vertex coloring of an undirected input graph G is said to be an H-FREE COLORING if none of the color classes contain H as an induced subgraph. The H-FREE CHROMATIC NUMBER of G is the minimum number of colors required for an H-FREE COLORING of G. Both The MATCHING CUT problem and the H-FREE COLORING problem can be expressed using a monadic second-order logic (MSOL) formula and hence is solvable in linear time for graphs with bounded tree-width. However, this approach leads to a running time of f(||φ||,t)nO(1), where ||φ|| is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. The dependency of f(||φ||,t) on ||φ|| can be as bad as a tower of exponentials. In this paper, we provide explicit combinatorial FPT algorithms for MATCHING CUT problem and H-FREE COLORING problem, parameterized by the tree-width of G. The single exponential FPT algorithm for the MATCHING CUT problem answers an open question posed by Kratsch and Le (2016). The techniques used in the paper are also used to provide an FPT algorithm for a variant of H-free coloring, where H is forbidden as a subgraph (not necessarily induced) in the color classes of G. © 2021 Elsevier B.V.

Discrete Applied Mathematics

Vertex partitioning problems on graphs with bounded tree width

The rapid expansion of the Industrial Internet of Things (IIoT) necessitates the digitization of industrial processes in order to increase network efficiency. The integration of Digital Twin (DT) with IIoT digitizes physical objects into virtual representations to improve data analytics performance. Nevertheless, DT empowered IIoT generates a massive amount of data that is mostly sent to the cloud or edge servers for real-time analysis. However, unreliable public communication channels and lack of trust among participating entities causes various types of threats and attacks on the ongoing communication. Motivated from the aforementioned discussion, we present a blockchain and Deep Learning (DL) integrated framework for delivering decentralized data processing and learning in IIoT network. The framework first present a new DT model that facilitates construction of a virtual environment to simulate and replicate security-critical processes of IIoT. Second, we propose a blockchain-based data transmission scheme that uses smart contracts to ensure integrity and authenticity of data. Finally, the DL scheme is designed to apply the Intrusion Detection System (IDS) against valid data retrieved from blockchain. In DL scheme, a Long Short Term Memory-Sparse AutoEncoder (LSTMSAE) technique is proposed to learn the spatial-temporal representation. The extracted characteristics are further used by the proposed Multi-Head Self-Attention (MHSA)-based Bidirectional Gated Recurrent Unit (BiGRU) algorithm to learn long-distance features and accurately detect attacks. The practical implementation of our proposed framework proves considerable enhancement of communication security and data privacy in DT empowered IIoT network. IEEE

Department of Electrical Engineering

Fulltext

IEEE Transactions on Network Science and Engineering

Blockchain and Deep Learning for Secure Communication in Digital Twin Empowered Industrial IoT Network

Network Functions Virtualization (NFV) replaces the conventional middleboxes by their software counterparts known as Virtual Network Functions (VNFs) which run on general-purpose hardware platforms and promise several benefits like reduced cost, ease of deployment, flexibility, etc. However, NFV faces some critical challenges as VNFs running on the same physical hardware still have to compete for shared resources such as Last Level Cache (LLC) and different levels of Memory Bandwidth (MB) (between L2 cache &amp; LLC and LLC &amp; main memory), which might result in unpredictable and variable performance interference to the co-located VNFs deployed. Some recent works have explored mechanisms for allocating LLC dynamically using Cache Allocation Technology (CAT) but they did not look into MB contentions among the co-located VNFs. Dynamic allocation of both LLC and MB to the co-located VNFs remains unexplored. To address this, in this work, by leveraging Intel's CAT and Memory Bandwidth Allocation (MBA) technologies, we profile different VNFs to determine their minimum LLC and MB resource requirements to achieve performance isolation for different input traffic rates. We then propose a dynamic, joint resource allocation scheme, RESTRAIN, that takes each VNF's input traffic rate as an input and dynamically adjusts LLC ways and MB resources allocated among them to avoid performance interference and thereby improves the overall resource utilization of the underlying hardware system and the number of VNFs meeting their QoS guarantees. Experimental results on a prototype system show that the proposed RESTRAIN scheme guarantees performance isolation. Further, it improves performance by 30% over a static allocation mechanism and 17% over ResQ, a state-of-the-art scheme. © 2022 Elsevier Ltd

Journal of Network and Computer Applications

RESTRAIN: A dynamic and cost-efficient resource management scheme for addressing performance interference in NFV-based systems

The object detection in aerial images is one of the most commonly used tasks in the wide-range of computer vision applications. However, the object detection is more challenging due to the following issues: (a) the pixel occupancy vary among the different scales of objects, (b) the distribution of objects is not uniform in aerial images, (c) the appearance of an object varies with different view-points and illumination conditions, and (d) the number of objects, even though they belong to same type, vary across the images. To address these issues, we propose a novel network for multi-scale object detection in aerial images using hierarchical dilated convolutions, called as mSODANet. In particular, we probe hierarchical dilated network using parallel dilated convolutions to learn the contextual information of different types of objects at multiple scales and multiple field-of-views. The introduced hierarchical dilated network captures the visual information of aerial image more effectively and enhances the detection capability of the model. Further, the extensive experiments conducted on three challenging publicly available datasets, i.e., Visdrone2019, DOTA (OBB & HBB), NWPU VHR-10, demonstrate the effectiveness of the proposed mSODANet and achieve the state-of-the-art performance on all three datasets. © 2022 Elsevier Ltd

Pattern Recognition

mSODANet: A network for multi-scale object detection in aerial images using hierarchical dilated convolutions

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. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

Algorithmica

On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

Vertex-deletion problems have been at the heart of parameterized complexity throughout its history. Here, the aim is to determine the minimum size (denoted by modℋ) of a modulator to a graph class ℋ, i.e., a set of vertices whose deletion results in a graph in ℋ. Recent years have seen the development of a research programme where the complexity of modulators is measured in ways other than size. For instance, for a graph class ℋ, the graph parameters elimination distance to ℋ (denoted by edℋ) [Bulian and Dawar, Algorithmica, 2016] and ℋ-treewidth (denoted by twℋ) [Eiben et al. JCSS, 2021] aim to minimize the treedepth and treewidth, respectively, of the "torso"of the graph induced on a modulator to the graph class ℋ. Here, the torso of a vertex set S in a graph G is the graph with vertex set S and an edge between two vertices u, v S if there is a path between u and v in G whose internal vertices all lie outside S. In this paper, we show that from the perspective of (non-uniform) fixed-parameter tractability (FPT), the three parameters described above give equally powerful parameterizations for every hereditary graph class ℋ that satisfies mild additional conditions. In fact, we show that for every hereditary graph class ℋ satisfying mild additional conditions, with the exception of edℋ parameterized by twℋ, for every pair of these parameters, computing one parameterized by itself or any of the others is FPT-equivalent to the standard vertex-deletion (to ℋ) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem implies a non-uniform FPT algorithm for computing edℋ and twℋ. The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if ℋ is hereditary, union-closed, CMSO-definable, and (a) the canonical equivalence relation (or any refinement thereof) for membership in the class can be efficiently computed, or (b) the class admits a "strong irrelevant vertex rule", then there exists a uniform FPT algorithm for edℋ. Using these sufficient conditions, we obtain uniform FPT algorithms for computing edℋ, when ℋ is defined by excluding a finite number of connected (a) minors, or (b) topological minors, or (c) induced subgraphs, or when ℋ is any of bipartite, chordal or interval graphs. For most of these problems, the existence of a uniform FPT algorithm has remained open in the literature. In fact, for some of them, even a non-uniform FPT algorithm was not known. For example, Jansen et al. [STOC 2021] ask for such an algorithm when ℋ is defined by excluding a finite number of connected topological minors. We resolve their question in the affirmative. Copyright © 2022 by SIAM.

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent

Given two graphs G and H, and a list L(u) ⊆ V(H) associated with each u∈ V(G), a list homomorphism from G to H is a mapping f: V(G) → V(H) such that (i) for all u∈ V(G), f(u) ∈ L(u), and (ii) for all u, v∈ V(G), if uv∈ E(G) then f(u) f(v) ∈ E(H). The List Homomorphism problem asks whether there exists a list homomorphism from G to H. Enright, Stewart and Tardos [SIAM J. Discret. Math., 2014] showed that the List Homomorphism problem can be solved in O(nk2-3k+4) time on graphs where every connected induced subgraph of G admits “a multichain ordering” (see the introduction for the definition of multichain ordering of a graph), that includes permutation graphs, biconvex graphs, and interval graphs, where n= | V(G) | and k= | V(H) |. We prove that List Homomorphism parameterized by k even when G is a bipartite permutation graph is W[1]-hard. In fact, our reduction implies that it is not solvable in time no(k), unless the Exponential Time Hypothesis (ETH) fails. We complement this result with a matching upper bound and another positive result. 1.There is a O(n8k+3) time algorithm for List Homomorphism on bipartite graphs that admit a multichain ordering that includes the class of bipartite permutation graphs and biconvex graphs.2.For bipartite graph G that admits a multichain ordering, List Homomorphism is fixed parameter tractable when parameterized by k and the number of layers in the multichain ordering of G. In addition, we study a variant of List Homomorphism called List Locally Surjective Homomorphism. We prove that List Locally Surjective Homomorphism parameterized by the number of vertices in H is W[1]-hard, even when G is a chordal graph and H is a split graph. © 2022, Springer Nature Switzerland AG.