Department of Computer Science and Engineering

Indian Institute of Technology Palakkad&nbsp;(IIT Palakkad or IIT PKD) is a public autonomous&nbsp;engineering&nbsp;and&nbsp;research&nbsp;institute located in&nbsp;Palakkad,&nbsp;Kerala. It was&nbsp;one of the five new&nbsp;IITs&nbsp;proposed in the&nbsp;2014 Union budget of India. The campus was inaugurated on 3 August 2015. The institute has 94 faculty, 978 students, and 63 non-teaching staffs.

IT Palakkad currently offers four-year Bachelor of Technology (B.Tech) and two years MS programmes in 8 different engineering disciplines including&nbsp;Computer Science, Electrical, Mechanical, Civil among others.

&nbsp;

IIT Palakkad

World University root node

Distributed Graph Analytics

Introduction to Graph Analytics

Efficient Parallel Implementation of Graph Algorithms

Validation of network state of Network Function Virtualization Infrastructure (NFVI) under various uncertainties are of primary importance as they directly affect Service Function Chain (SFC) provisioning and its performance. SFC provisioning against the uncertainties, including variable traffic demand and failures of link and switch makes validation challenging because the number of scenarios to validate grows exponentially with the number of such failures. This letter takes advantage of a two-stage validation framework and proposes a validation strategy to verify the underlying NFVI network state that supports SFC provisioning despite various uncertainty in the network. We demonstrate the effectiveness of our strategy through different failure and SFC placement scenarios using realistic network topologies and traffic matrix. © 1997-2012 IEEE.

IEEE Communications Letters

Predicting Dynamic Network State of SFC Operation with Uncertainties

This paper establishes a close relationship among the four information theoretic problems, namely Campbell source coding, Arikan guessing, Huleihel et al. memoryless guessing and Bunte and Lapidoth tasks partitioning problems. We first show that the aforementioned problems are mathematically related via a general moment minimization problem whose optimum solution is given in terms of Renyi entropy. We then propose a general framework for the mismatched version of these problems and establish all the asymptotic results using this framework. Further, we study an ordered tasks partitioning problem that turns out to be a generalisation of Arikan's guessing problem. Finally, with the help of this general framework, we establish an equivalence among all these problems, in the sense that, knowing an asymptotically optimal solution in one problem helps us find the same in all other problems.

arXiv e-prints, arXiv: 2012.

Are Guessing, Source Coding and Tasks Partitioning Birds of a Feather?

An orientation of an undirected graph G is an assignment of exactly one direction to each edge of G. The oriented diameter of a graph G is the smallest diameter among all the orientations of G. The maximum oriented diameter of a family of graphs (formula presented) is the maximum oriented diameter among all the graphs in (formula presented). Chvátal and Thomassen [JCTB, 1978] gave a lower bound of (formula presented) and an upper bound of (formula presented) for the maximum oriented diameter of the family of 2-edge connected graphs of diameter d. We improve this upper bound to (formula presented), which outperforms the former upper bound for all values of d greater than or equal to 8. For the family of 2-edge connected graphs of diameter 3, Kwok, Liu and West [JCTB, 2010] obtained improved lower and upper bounds of 9 and 11 respectively. For the family of 2-edge connected graphs of diameter 4, the bounds provided by Chvátal and Thomassen are 12 and 40 and no better bounds were known. By extending the method we used for diameter d graphs, along with an asymmetric extension of a technique used by Chvátal and Thomassen, we have improved this upper bound to 21. © Springer Nature Switzerland AG 2020.

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

An improvement to chvátal and thomassen’s upper bound for oriented diameter

For a Boolean function f:{0,1}n→{0,1} computed by a Boolean circuit C over a finite basis B, the energy complexity of C (denoted by ECB(C)) is the maximum over all inputs {0,1}n of the number gates of the circuit C (excluding the inputs) that output a one. Energy Complexity of a Boolean function over a finite basis B denoted by ECB(f)=defminC⁡ECB(C) where C is a Boolean circuit over B computing f. We study the case when B={∧2,∨2,¬}, the standard Boolean basis. It is known that any Boolean function can be computed by a circuit (with potentially large size) with an energy of at most 3n(1+ϵ(n)) for a small ϵ(n) (which we observe is improvable to 3n−1). We show several new results and connections between energy complexity and other well-studied parameters of Boolean functions. • For all Boolean functions f, EC(f)≤O(DT(f)3) where DT(f) is the optimal decision tree depth of f. • We define a parameter positive sensitivity (denoted by psens), a quantity that is smaller than sensitivity (Cook et al. 1986, [3]) and defined in a similar way, and show that for any Boolean circuit C computing a Boolean function f, EC(C)≥psens(f)/3. • For a monotone function f, we show that EC(f)=Ω(KW+(f)) where KW+(f) is the cost of monotone Karchmer-Wigderson game of f. • Restricting the above notion of energy complexity to Boolean formulas, we show EC(F)=Ω(L(F)−Depth(F)) where L(F) is the size and Depth(F) is the depth of a formula F. © 2020 Elsevier B.V.

Fulltext

Theoretical Computer Science

New bounds for energy complexity of Boolean functions

An r-partite tournament is a directed graph obtained by assigning a unique orientation to each edge of a complete undirected r-partite simple graph. Given a bipartite tournament T on n vertices, we explore the parameterized complexity of the problem of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k. Although the maximization version of this problem can be seen as the linear programming dual of the well-studied problem of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in bipartite tournaments, surprisingly no algorithmic results seem to exist. We show that this problem can be solved in 2O(k log k)nO(1) time and admits a kernel with O(k2) vertices. © Springer Nature Switzerland AG 2020.

Packing arc-disjoint cycles in bipartite tournaments

Vertex deletion problems on graphs involve finding a set of minimum number of vertices whose deletion results in a graph with some specific property. In a recent study on vertex deletion problems on split graphs, it was shown that transforming a split graph to a block graph or a threshold graph using minimum number of vertex deletions is NP-hard. We call the decision version of these problems as Split to Block Vertex Deletion (SBVD) and Split to Threshold Vertex Deletion (STVD), respectively. In this paper, we study the parameterized complexity of these problems with the number of vertex deletions, k, as a parameter. These problems are implicit 4-Hitting Set and thus admit an algorithm with running time&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML"><msup is="true"><mrow is="true"><mi mathvariant="script" is="true">O</mi></mrow><mrow is="true"><mo is="true">⋆</mo></mrow></msup><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mn is="true">3.0755</mn></mrow><mrow is="true"><mi is="true">k</mi></mrow></msup><mo stretchy="false" is="true">)</mo></math>, a kernel with&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script" is="true">O</mi><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">k</mi></mrow><mrow is="true"><mn is="true">3</mn></mrow></msup><mo stretchy="false" is="true">)</mo></math>&nbsp;vertices, and a 4-approximation algorithm. In this paper, we exploit the structural properties of the concerned graph classes and obtain a kernel for SBVD with&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script" is="true">O</mi><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">k</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup><mo stretchy="false" is="true">)</mo></math>&nbsp;vertices and FPT algorithms for SBVD and STVD with running times&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML"><msup is="true"><mrow is="true"><mi mathvariant="script" is="true">O</mi></mrow><mrow is="true"><mo is="true">⋆</mo></mrow></msup><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mn is="true">2.3028</mn></mrow><mrow is="true"><mi is="true">k</mi></mrow></msup><mo stretchy="false" is="true">)</mo></math>&nbsp;and&nbsp;<math xmlns="http://www.w3.org/1998/Math/MathML"><msup is="true"><mrow is="true"><mi mathvariant="script" is="true">O</mi></mrow><mrow is="true"><mo is="true">⋆</mo></mrow></msup><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mn is="true">2.7913</mn></mrow><mrow is="true"><mi is="true">k</mi></mrow></msup><mo stretchy="false" is="true">)</mo></math>, respectively. We further give improved approximation algorithms for SBVD and STVD.

Vertex deletion on split graphs: Beyond 4-hitting set

We present challenges faced in making a domain-specific language (DSL) for graph algorithms adapt to varying requirements of generating a spectrum of efficient parallel codes. Graph algorithms are at the heart of several applications, and achieving high performance on graph applications has become critical due to the tremendous growth of irregular data. However, irregular algorithms are quite challenging to auto-parallelize, due to access patterns influenced by the input graph - which is unavailable until execution. Former research has addressed this issue by designing DSLs for graph algorithms, which restrict generality but allow efficient codegeneration for various backends. Such DSLs are, however, too rigid, and do not adapt to changes. For instance, these DSLs are incapable of changing the way of processing if the underlying graph changes. As another instance, most of the DSLs do not support more than one backends. We narrate our experiences in making an existing DSL, named Falcon, adaptive. The biggest challenge in the process is to retain the DSL code for specifying the underlying algorithm, and still generate different backend codes. We illustrate the effectiveness of our proposal by auto-generating codes for vertex-based versus edge-based graph processing, synchronous versus asynchronous execution, and CPU versus GPU backends from the same specification. © 2020 Association for Computing Machinery.