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

Stretch is a metric in the construction of spanning trees that measures the deviation in the distance between a pair of nodes in the tree compared to its shortest distance in the underlying graph. This paper proposes a silent self-stabilizing low stretch spanning tree construction protocol BuildTree, that is based on a Low Diameter Decomposition (LDD) technique. The LDD involves steps wherein the graph is decomposed into a small number of connected blocks or clusters, each having a low diameter value. The proposed BuildTree algorithm generates a spanning tree with an average stretch of nO ( 1 ) and converges to a correct configuration in O(n+ Δ· η) rounds, where n, Δ and η is the number of nodes in the graph, the maximum size of a cluster and the number of clusters, respectively. To the best of our knowledge, this is the first known work of using self-stabilization in order to make low stretch tree constructions fault-tolerant. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

World University root node

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

A Self-stabilizing Minimum Average Stretch Spanning Tree Construction

Diffusion is a natural phenomenon in many real-world networks. Spreading of ideas, rumors in an online social network; propagation of virus, malware in a computer network; spreading of diseases in a human contact network, etc. are some real-world examples of this. Diffusion often starts from a set of initial nodes known as seed nodes. A node can be in any one of the following two states: influenced (active) or not influenced (inactive). We assume that a node can change its state from inactive to active, however, not vice versa. Only the seed nodes are active initially and the information is dissipated from these seed nodes in discrete time steps. Each node v is associated with a threshold value τ(v) which is a positive integer. A node v will be influenced at time step t′, if there are at least τ(v) number of nodes in its neighborhood which have been activated on or before time step t′− 1. The diffusion stops when no more node-activation is possible. Given a simple, undirected graph G with a threshold function τ: V(G) → ℕ, the Target Set Selection (TSS) problem is about choosing a minimum cardinality set, say S⊆ V(G) , such that starting a diffusion process with S as its seed set will eventually result in activating all the nodes in G. For any non-negative integer i, we say a set T⊆ V(G) is a degree-imodulator of G if the degree of any vertex in the graph G − T is at most i. Degree-0 modulators of a graph are precisely its vertex covers. Consider a graph G on n vertices and m edges. We have the following results on the TSS problem: It was shown by Nichterlein et al. (Soc. Netw. Anal. Min. 3(2), 233–256 10) that it is possible to compute an optimal-sized target set in O(2(2t+1)t⋅m) time, where t denotes the cardinality of a minimum degree-0 modulator of G. We improve this result by designing an algorithm running in time 2O(tlogt)n.We design a 22O(t)nO(1) time algorithm to compute an optimal target set for G, where t is the size of a minimum degree-1 modulator of G.We show that for a graph on n vertices of treewidth s, the TSS problem cannot be solved in f(s)no(slogs) time unless the Exponential Time Hypothesis fails. This is an improvement over the previously known lower bound of f(s)no(s) due to Ben-Zwi et al. (Discret. Optim. 8(1), 87–96 16). In fact, we prove that same lower bound holds when parameterized by tree-depth or star-deletion number. © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

Theory of Computing Systems

Target Set Selection Parameterized by Vertex Cover and More

Targeted data breaches and cybersecurity attacks involving IoT devices are becoming ever more concerning. To combat these threats and risks, the IETF standardized Manufacturer Usage Description (MUD), which allows IoT device vendors to specify the intended communication patterns (MUD profile) of an IoT device. MUD profile enables validation of the actual communication pattern of an IoT device with the intended behavior at run-time. However, the MUD specification was primarily intended for enforcement at the Local Area Network (LAN) of the IoT device, thus fragmenting the solution across multiple heterogeneous networks. MUD enforcement at higher levels in the network hierarchy (e.g., private edge for enterprise networks) eases security policy management and reduces processing overheads on the existing security infrastructure. To realize MUD enforcement at the edge, there are mainly two challenges: (1) How to identify an IoT device at the edge so that enforcing device-specific MUD profile on the IoT traffic is possible. (2) How to scale MUD enforcement to a large network of IoT devices. In this paper, we present our approach to address these challenges and validate IoT device communication at the edge. In order to scale MUD enforcement to a large IoT network, we leverage multi-stage pipeline architecture and stateful ALUs of P4 programmable switch and process IoT traffic in the dataplane. © 2022 ACM.

FFSPIN 2022 - Proceedings of the ACM SIGCOMM 2022 Workshop on Formal Foundations and Security of Programmable Network Infrastructures

IoT MUD enforcement in the edge cloud using programmable switch

Performance monitoring and diagnosis are essential for data centers. The emergence of programmable switches has led to the development of a slew of monitoring systems, but most of them do not explicitly target posterior diagnosis. On one hand, “query-driven” monitoring systems must be pre-configured with a static query, but it is difficult to achieve high coverage because the right query for posterior diagnosis may not be known in advance. On the other hand, “blanket” monitoring systems have high coverage as they always collect telemetry data from all switches, but they collect excessive data. SpiderMon is a system that co-designs monitoring and posterior diagnosis in a closed loop to achieve low overhead and high coverage simultaneously, by leveraging “wait-for” relations to guide its operations. We evaluate SpiderMon in both Tofino hardware and BMv2 software switches and show that SpiderMon diagnoses performance problems accurately and quickly with low overhead. © 2022 by The USENIX Association. All Rights Reserved.

Proceedings of the 19th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2022

Closed-loop Network Performance Monitoring and Diagnosis with SpiderMon

Circular trading is a form of tax evasion in Goods and Services Tax where a group of fraudulent taxpayers (traders) aims to mask illegal transactions by superimposing several fictitious transactions ( where no value is added to the goods or service) among themselves in a short period. Due to the vast database of taxpayers, it is infeasible for authorities to manually identify groups of circular traders and the illegitimate transactions they are involved in. This work uses big data analytics and graph representation learning techniques to propose a framework to identify communities of circular traders and isolate the illegitimate transactions in the respective communities. Our approach is tested on real-life data provided by the Department of Commercial Taxes, Government of Telangana, India, where we uncovered several communities of circular traders. © 2022 IEEE.

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

Representation Learning on Graphs to Identifying Circular Trading in Goods and Services Tax

Computing the angular similarity between pairs of vectors is a core part of various machine learning algorithms. The seminal work of Charikar [Charikar, 2002] (a.k.a. Sign-Random-Projection (SRP) or SimHash) provides an unbiased estimate for the same. However, SRP suffers from the following limitations: (i) large variance in the similarity estimation, (ii) and high running time while computing the sketch. There are improved variants that address these limitations. However, they are known to improve on only one aspect in their proposal, for e.g. [Yu et al., 2014] suggest a faster algorithm, [Ji et al., 2012, Kang and Wong, 2018] provide estimates with a smaller variance. In this work, we propose a sketching algorithm that addresses both aspects in one algorithm - a faster algorithm along with a smaller variance in the similarity estimation. Moreover, our algorithm is space-efficient as well. We present a rigorous theoretical analysis of our proposal and complement it via experiments on synthetic and real-world datasets. © 2022 UAI. All Rights Reserved.

Proceedings of Machine Learning Research

Improving Sign-Random-Projection via Count Sketch

Deep learning Processor Units (DPUs) from Xilinx are design-time configurable CNN accelerators for FPGAs. We propose EXPRESS, which predicts the execution time of any given CNN on a DPU. EXPRESS incorporates the effect of bus connections into prediction. As a DPU is invoked by a host CPU to process a CNN layer by layer, EXPRESS considers the CPU and the DPU execution time for predicting the end-to-end processing time. EXPRESS has an average prediction error of 2.2% and significantly outperforms state-of-the-art. © 2022 IEEE.

FPT 2022 - 21st International Conference on Field-Programmable Technology, Proceedings

EXPRESS: CNN EXecution Time PREdiction for DPU DeSign Space Exploration

Identification and categorization of social media posts generated during disasters are crucial to reduce the suffering of the affected people. However, the lack of labeled data is a significant bottleneck in learning an effective categorization system for a disaster. This motivates us to study the problem as unsupervised domain adaptation (UDA) between a previous disaster with labeled data (source) and a current disaster (target). However, if the amount of labeled data available is limited, it restricts the learning capabilities of the model. To handle this challenge, we use limited labeled data along with abundantly available unlabeled data, generated during a source disaster to propose a novel two-part graph neural network (GNN). The first part extracts domain-agnostic global information by constructing a token-level graph across domains and the second part preserves local instance-level semantics. In our experiments, we show that the proposed method outperforms state-of-the-art techniques by 2.74&#x0025; weighted F&#x2081; score on average on two standard public datasets in the area of disaster management. We also report experimental results for granular actionable multilabel classification datasets in disaster domain for the first time, on which we outperform BERT by 3.00&#x0025; on average w.r.t. weighted F&#x2081;. Additionally, we show that our approach can retain performance when minimal labeled data are available. IEEE

IEEE Transactions on Computational Social Systems

Unsupervised Domain Adaptation With Global and Local Graph Neural Networks Under Limited Supervision and Its Application to Disaster Response

In second or foreign language (SFL) education, oral corrective feedback (OCF) is widely used to individually correct students’ erroneous utterances during classroom hours. However, students cannot have sufficient opportunities for oral production and personalized feedback during classroom hours if a class is large-scale with many students. This paper addresses the lack of OCF opportunities in a large-scale class, assuming the causes to be the severe time constraints and the teachers’ labor intensiveness in examining students’ utterances and generating OCF. This research proposes using computer-mediated feedback (CMF) outside classroom hours to complement OCF in an online, semiautomated, and scalable fashion. This paper implements Oral Repetition Practice (ORP) Gym to provide students with sufficient opportunities for speaking practice through two types of CMFs; Hybrid Recast to enhance the recognition of errors and Explicit Error Correction to make errors detectable and correctable. Online External Assistant (OEA) is a mechanism used to increase the amount and quality of feedback by distributing the workload for scoring and generating CMF. The evaluation was conducted as a classroom observational study by introducing ORP Gym to a spoken Japanese SFL basics course with 55 students at an Indian university. Compared with the students who did not utilize ORP Gym, those who utilized ORP Gym performed more ORP and exhibited significant score improvement in the posttest. This research contributes to enabling CMF in large-scale SFL classes and empirically and statistically proving the improvement of the learning effect, including uptake and repair, by CMF using ORP Gym and an OEA. © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

Fulltext

Education and Information Technologies

Investigating the effect of computer-mediated feedback via an LMS integration in a large-scale Japanese speaking class

The local boxicity of a graph G, denoted by lbox(G), is the minimum positive integer l such that G can be obtained using the intersection of k (where k≥l) interval graphs where each vertex of G appears as a non-universal vertex in at most l of these interval graphs. Let G be a graph on n vertices having m edges. Let Δ denote the maximum degree of a vertex in G. We show that, • lbox(G)≤213log⁎⁡ΔΔ. • lbox(G)∈O([Formula presented]). • lbox(G)≤(213log⁎⁡m+2)m. • the local boxicity of G is at most its product dimension. This connection helps us in showing that the local boxicity of the Kneser graph K(n,k) is at most [Formula presented]log⁡log⁡n. The above results can be extended to the local dimension of a partially ordered set due to the known connection between local boxicity and local dimension. Using this connection along with known results it can be shown that there exist graphs of maximum degree Δ having a local boxicity of Ω([Formula presented]). There also exist graphs on n vertices and graphs on m edges having local boxicity of Ω([Formula presented]) and Ω([Formula presented]), respectively. © 2022 Elsevier B.V.