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

In the Euclidean k-Means problem we are given a collection of n points D in an Euclidean space and a positive integer k. Our goal is to identify a collection of k points in the same space (centers) so as to minimize the sum of the squared Euclidean distances between each point in D and the closest center. This problem is known to be APX-hard and the current best approximation ratio is a primal-dual 6.357 approximation based on a standard LP for the problem [Ahmadian et al. FOCS'17, SICOMP'20]. In this note we show how a minor modification of Ahmadian et al.'s analysis leads to a slightly improved 6.12903 approximation. As a related result, we also show that the mentioned LP has integrality gap at least [Formula presented]. © 2022 The Author(s)

World University root node

Information Processing Letters

A refined approximation for Euclidean k-means

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

Preface

A graph G on n vertices is a threshold graph if there exist real numbers $$a:1,a_2, \ldots, a_n$$ and b such that the zero-one solutions of the linear inequality $$\sum \limits _{i=1}^n a_i x_i \le b$$ are the characteristic vectors of the cliques of G. Introduced in [Aggregation of inequalities in integer programming. Chvátal and Hammer, Annals of Discrete Mathematics, 1977], the threshold dimension of a graph G, denoted by $$\textrm{dim}:{\textrm{TH}}(G)$$, is the minimum number of threshold graphs whose intersection yields G. Given a graph G on n vertices, in line with Chvátal and Hammer, $$f:G_\{0,1\}^n \rightarrow \{0,1\}$$ is the Boolean function that has the property that $$f:G(x) = 1$$ if and only if x is the characteristic vector of a clique in G. A Boolean function f for which there exists a graph G such that $$f=f:G$$ is called a graphic Boolean function. It follows that for a graph G, $$\textrm{dim}:{\textrm{TH}}(G)$$ is precisely the minimum number of majority gates whose AND (or conjunction) realizes the graphic Boolean function $$f:G$$. The fact that there exist Boolean functions which can be realized as the AND of only exponentially many majority gates motivates us to study threshold dimension of graphs. We give tight or nearly tight upper bounds for the threshold dimension of a graph in terms of its treewidth, maximum degree, degeneracy, number of vertices, size of a minimum vertex cover, etc. We also study threshold dimension of random graphs and graphs with high girth. © 2022, Springer Nature Switzerland AG.

Bounding Threshold Dimension: Realizing Graphic Boolean Functions as the AND of Majority Gates

Social Information Seeking (SIS) is a platform for easy and informal interaction among participants. This has been popularized by many of the major prevailing Community Question Answering (CQA) forums, such as Quora, Stackoverflow, etc. A user submits a question to the forum that is later answered by one or more of the users in the forum. These sites facilitate knowledge exchange between users through questions and answers. A large pool of knowledge has since been created. Although hundreds of questions are posted every hour, many of them remain unanswered due to lower quality, wrong choice of question tags, bad routing of questions to experts, and dearth of proper answerers. In this paper, we propose a solution to the problem of routing questions to appropriate experts by utilizing the tag and time information of the posted questions. We propose a recommendation model that uses a tag network and temporal analysis to find the potential experts. Our experiments over a dataset from Stack Exchange show the effectiveness of our approach over several baseline models. © 2022, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

Communications in Computer and Information Science

DACE: Did I Catch You at a Good Time?

The softwarized infrastructure of Software-Defined Industrial Internet of Things (SDIIoT) offers a cost-effective solution to improve flexibility and reliability in network management but faces several critical challenges. First, th Majority of SDIIoT entities operate over wireless channel, which expose them to a variety of attacks (e.g., man-in-the-middle, replay, and impersonation attacks) and also the centralized nature of SDN controller is prone to single point attacks. Second, network traffic in the SDIIoT is associated with large scale, high dimension and redundant data, all of which present significant hurdles in the development of efficient flow analyzer. In this regard, we present a novel blockchain and Deep Learning (DL) integrated framework for protecting confidential information and hunting cyber threats against SDIIoT and their network traffic. First the blockchain module is proposed to securely transmit industrial data from IIoT sensors to controllers of SDN via forwarding nodes (i.e., OpenFLow switches) using Clique Proof-of-Authority (C-PoA) consensus mechanism. A novel flow analyzer based on DL architecture named LSTMSCAE-AGRU is designed by combining Long Short-Term Memory Stacked Contractive AutoEncoder (LSTMSCAE) with Attention-based Gated Recurrent Unit (AGRU) at the control plane. The latter first extracts low-dimensional features in an unsupervised manner, which is then fed to AGRU for hunting anomalous switch requests. The proposed framework can withstand a variety of well-known cyber threats and mitigate the single point of controller failure problem in SDIIoT. © 2022 IEEE.

Department of Electrical Engineering

2022 IEEE International Conference on Communications Workshops, ICC Workshops 2022

Blockchain and Deep Learning for Cyber Threat-Hunting in Software-Defined Industrial IoT

To reduce the processing delay from the sequentially running virtual network functions (VNFs) in a service function chain (SFC), network function parallelism (NFP) is introduced that allows VNFs of the SFC to run in parallel. Existing NFP solutions only focused on improving parallelism benefits without paying much attention to resource utilization while deploying VNFs of SFCs. We take advantage of resource-delay dependency to propose a flexible and efficient parallelized SFC placement mechanism called FlexSFC which determines the optimal SFC placement while reducing resource usage and meeting end-to-end delay guarantees of the SFCs deployed. Initial results show that FlexSFC guarantees the end-to-end delay requirement with better resource utilization and SFC acceptance rate than the state-of-the-art approaches. © 2022 IEEE.

Proceedings of the 2022 IEEE International Conference on Network Softwarization: Network Softwarization Coming of Age: New Challenges and Opportunities, NetSoft 2022

FlexSFC: Flexible Resource Allocation and VNF Parallelism for Improved SFC Placement

The recent adaption of virtualization technologies in the next generation mobile network enables 5G base station to be segregated into a Radio Unit (RU), a Distributed Unit (DU), and a Central Unit (CU) to support Cloud based Radio Access Networks (C-RAN). RU and DU are connected through a fronthaul link. In contrast, CU and DU are connected through a midhaul link. Although virtualization of CU gives benefits of centralization to the operators, there are other issues to be solved such as optimization of midhaul bandwidth and computing resources at edge cloud and central cloud where the DUs and CUs are deployed, respectively. In this paper, we propose a dynamic functional split selection for the DUs in 5G C-RAN by adopting to traffic heterogeneity where the midhaul bandwidth is limited. We propose an optimization problem that maximizes the centralization of the C-RAN system by operating more number of DUs on split Option-7 by changing the channel bandwidth of the DUs. The dynamic selection of split options among each CU-DU pair gives 90% centralization over the static functional split for a given midhaul bandwidth. © 2022 IEEE.

Traffic-Aware Dynamic Functional Split for 5G Cloud Radio Access Networks

In the List Coloring problem, the input is a graph G and list of colors L: V(G) → N for each vertex v∈ V(G). The objective is to test the existence of a coloring λ: V(G) → N such that for each v∈ V(G), λ(v) ∈ L(v) and for each edge (u, v) ∈ E(G), λ(u) ≠ λ(v). Fiala et al. (TCS 2011) proved that List Coloring is W[1]-hard when parameterized by the vertex cover number of the input graph. Recently, Gutin et al. (STACS 2020, SIDMA 2021) designed an O∗(2 k) time randomized algorithm for List Coloring where k is the size of the given clique modulator of the input graph. Since List Coloring is W[1]-hard parameterized by the vertex cover number, List Coloring is W[1]-hard parameterized by the size of a cluster modulator. In this work we study the problem parameteized by the size of ℓ -cluster modulator. That is, along with the input we are also given a vertex subset D such that G- D is cluster graph with ℓ connected components. We prove that assuming Exponential Time Hypothesis (ETH), List Coloring can not be solved in time f(|D|+ℓ)no(|D|+ℓlog|D|+ℓ) for any computable function f. In the Max Coloring problem, we are given a graph G and a weight function w: V(G) → N. For a proper coloring λ, the cost of λ is defined as follows. For each color i, w(i) is the maximum weight of a vertex colored i. Then, the cost of λ is ∑ i∈Cw(i), where C={λ(v)|v∈V(G)}. In the Max Coloring problem, our objective is to find a proper coloring with minimum cost. Araújo et al. (TCS 2018) proved that Max Coloring is W[1]-hard even on forests when parameterized by the size of the largest connected component in the input forest. Here, we prove that Max Coloring is FPT with respect to parameters (i) the size of a vertex cover, (ii) the size of a clique modulator, and (iii) the size of a 2-cluster modulator. © 2022, Springer Nature Switzerland AG.

Parameterized Complexity of List Coloring and Max Coloring

In the Partial Vertex Cover (PVC) problem, we are given an n-vertex graph G and a positive integer k, and the objective is to find a vertex subset S of size k maximizing the number of edges with at least one end-point in S. This problem is W[1]-hard on general graphs, but admits a parameterized subexponential time algorithm with running time 2O(k)nO(1) on planar and apex-minor free graphs [Fomin et al. (FSTTCS 2009, IPL 2011)], and a kO(k)nO(1) time algorithm on bounded degeneracy graphs [Amini et al. (FSTTCS 2009, JCSS 2011)]. Graphs of bounded degeneracy contain many sparse graph classes like planar graphs, H-minor free graphs, and bounded tree-width graphs (see Fig. 1). In this work, we prove the following results: There are algorithms for PVC on graphs of degeneracy d with running time 2 O(dk)nO(1) and (e+ ed) k2 o(k)nO(1) which are improvements on the previous kO(k)nO(1) time algorithm by Amini et al. [2]PVC admits a polynomial compression on graphs of bounded degeneracy, resolving an open problem posed by Amini et al. [2]. © 2022, Springer Nature Switzerland AG.

Partial Vertex Cover on Graphs of Bounded Degeneracy

The hybrid software-defined networks (SDN) architectures are beneficial for a smooth transition and less costly SDN deployment. However, legacy switches and SDN switches coexistence brings new challenges of deployment inconsistency management and security. Security is not well studied for hybrid SDN architecture. In this paper, we study the topology poisoning attacks in hybrid SDN for the first time. We propose new attack vectors for link fabrication in hybrid SDN. The new attack is named 'multi-hop link fabrication,' in which an adversary successfully injects a fake multi-hop link (MHL) by exploiting the link discovery protocols. We presented the Hybrid-Shield, a link verification framework for hybrid SDN link discovery. Hybrid-Shield introduces a novel verification technique that includes: i) monitoring legacy switch and host generated traffic at MHL and ii) validating the existence of legacy switches contained in an MHL. This paper presents the prototype implementation of Hybrid-Shield over a real SDN controller. The experimental evaluation is performed with the mininet virtual network emulation. Our evaluation shows that Hybrid-Shield is capable of detecting MHL fabrication attacks in real-time with high accuracy. Hybrid-Shield's performance evaluation shows that it is lightweight at the controller as it causes less overhead and requires no additional functionalities at the SDN controller for deployment. © 2022 IEEE.