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

It is known, from the work of Dai et al. (in CRYPTO’17), that the PRF advantage of XORP (bitwise-xor of two outputs of n-bit random permutations with domain separated inputs), against an adversary making q queries, is about q/ 2n for q≤ 2n - 5. The same bound can be easily shown to hold for XORP[ k] (bitwise-xor of k outputs n-bit pseudorandom random permutations with domain separated inputs), for k≥ 3. In this work, we first consider multi-user security of XORP[ 3 ]. We show that the multi-user PRF advantage of XORP[ 3 ] is about uqmax/2n for all qmax≤ 2n/ 12, where u is the number of users and qmax is the maximum number of queries the adversary can make to each user. In the multi-user setup, this implies that XORP[ 3 ] gives security for O(2n) users even allowing almost O(2n) queries to each user. This also indicates significant improvement in the single-user setup (i.e., when u= 1 ), where the distinguishing advantage of the adversary even after making O(2n) queries is O(12n), i.e., negligible. Subsequently, we consider a simple efficient variant of XORP[ 3 ] in which we use five calls to produce 2n bit output (instead of six calls in the case of XORP[ 3 ] ). This variant also achieves similar level of security. As an immediate application, we can construct a variant of block cipher based counter mode which provides much higher security (both in the single-user and the multi-user setup) compared to the security of the encryption part of GCM at the cost of efficiency. © 2021, International Association for Cryptologic Research.

World University root node

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

Luby-Rackoff Backwards with More Users and More Security

arXiv preprint arXiv:2108.

An ensemble of high rank matrices arising from tournaments

Intelligent Electrical Systems: A Step towards Smarter Earth

Natural Ground-Water Recharge Scenario in Kolkata and a Review of Artificial Recharging

Rapid device aging in the nano era threatens system lifetime reliability, posing a major intrinsic threat to system functionality. Traditional techniques to overcome the aging-induced device slowdown, such as guardbanding are static and incur performance, power, and area penalties. In a manycore processor, the system-level design abstraction offers dynamic opportunities through the control of task-to-core mappings and per-core operation frequency towards more balanced core aging profile across the chip, optimizing the system lifetime reliability while meeting the application performance requirements. This article presents Longevity Framework (LF) that leverages online integrated aging-aware hierarchical mapping and voltage frequency (VF)-selection for lifetime reliability optimization in manycore processors. The mapping exploration is hierarchical to achieve scalability. The VF-selection builds on the trade-offs involved between power, performance, and aging as the VF is scaled while leveraging the per-core DVFS capabilities. The methodology takes the chip-wide process variation into account. Extensive experimentation, comparing the proposed approach with two state-of-the-art methods, for 64-core and 256-core systems running applications from PARSEC and SPLASH-2 benchmark suites, show an improvement of up to 3.2 years in the system lifetime reliability and 4× improvement in the average core health. © 2020 IEEE.

IEEE Transactions on Computers

Longevity Framework: Leveraging Online Integrated Aging-Aware Hierarchical Mapping and VF-Selection for Lifetime Reliability Optimization in Manycore Processors

A class domination coloring (also called cd-Coloring or dominated coloring) of a graph is a proper coloring in which every color class is contained in the neighborhood of some vertex. The minimum number of colors required for any cd-coloring of G, denoted by χcd(G), is called the class domination chromatic number (cd-chromatic number) of G. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity. (1) Given a graph G on n vertices, find its cd-chromatic number. (2) Given a graph G and integers k and q, can we delete at most k vertices such that the cd-chromatic number of the resulting graph is at most q? For the first problem, we give an exact algorithm with running time O(2nn4logn). Also, we show that the problem is FPT with respect to the number q of colors as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with O(q3) vertices. For the second (deletion) problem, we show NP-hardness for each q≥2. Further, on split graphs, we show that the problem is NP-hard if q is a part of the input and FPT with respect to k and q as combined parameters. As recognizing graphs with cd-chromatic number at most q is NP-hard in general for q≥4, the deletion problem is unlikely to be FPT when parameterized by the size of the deletion set on general graphs. We show fixed parameter tractability for q∈{2,3} using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines. © 2020 Elsevier B.V.

Discrete Applied Mathematics

Parameterized and exact algorithms for class domination coloring

A collection of linear orders on X, say L, is said to realize a partially ordered set (or poset) P= (X, ≼) if, for any two distinct x,y ∈ X, x ≼ y if and only if x ≺Ly, ∀ L∈ L. We call L a realizer of P. The dimension of P, denoted by dim(P) , is the minimum cardinality of a realizer of P. A containment modelMP of a poset P= (X, ≼) maps every x ∈ X to a set Mx such that, for every distinct x,y ∈ X, x ≼ y if and only if Mx⫋ My. We shall be using the collection (Mx)x∈X to identify the containment model MP. A poset P= (X, ≼) is a Containment order of Paths in a Tree (CPT poset), if it admits a containment model MP=(Px)x∈X where every Px is a path of a tree T, which is called the host tree of the model. We show that if a poset P admits a CPT model in a host tree T of maximum degree Δ and radius r, then dim(P)≤lglgΔ+(12+o(1))lglglgΔ+lgr+12lglgr+12lgπ+3. This bound is asymptotically tight up to an additive factor of min(12lglglgΔ,12lglgr). Further, let P(1 , 2 ; n) be the poset consisting of all the 1-element and 2-element subsets of [n] under ‘containment’ relation and let dim(1,2;n) denote its dimension. The proof of our main theorem gives a simple algorithm to construct a realizer for P(1 , 2 ; n) whose cardinality is only an additive factor of at most 32 away from the optimum. © 2020, Springer Nature B.V.

Order

Dimension of CPT Posets

Let G be a graph with no isolated vertices. A k-coupon coloring of G is an assignment of k colors to the vertices of G such that every vertex contains vertices of all k colors in its neighborhood. The coupon chromatic number of G, denoted χc(G), is the maximum k for which a k-coupon coloring exists. In this paper, we present an upper bound for the coupon chromatic number of Cartesian product of graphs G and H in terms of |V(G)| and |V(H)|. Further, we prove that if G and H are bipartite graphs then G□ H has a coupon coloring with 2 min { χc(G), χc(H) } colors. As consequences, for any positive integer n, we obtain the coupon chromatic number and total domination number of n-dimensional torus □i=1nCki with some suitable conditions to each ki, which turns out to be a generalization of the result due to S. Gravier [Total domination number of grid graphs, Discrete Appl. Math. 121 (2002) 119–128]. Finally, for any r≥ 0, d≥ 2, we obtain the coupon coloring for the Hamming graph Kd□ Kd□ ⋯ □ Kd (2r times). © 2021, Springer Nature Switzerland AG.

On Coupon Coloring of Cartesian Product of Some Graphs

The eternal vertex cover problem is a variant of the classical vertex cover problem defined in terms of an infinite attacker–defender game played on a graph. In each round of the game, the defender reconfigures guards from one vertex cover to another in response to a move by the attacker. The minimum number of guards required in any winning strategy of the defender when this game is played on a graph G is the eternal vertex cover number of G, denoted by evc(G). It is known that given a graph G and an integer k, checking whether evc(G)≤k is NP-hard. Further, it is known that for any graph G, mvc(G)≤evc(G)≤2mvc(G), where mvc(G) is the vertex cover number of G. Though a characterization is known for graphs for which evc(G)=2mvc(G), a characterization of graphs for which evc(G)=mvc(G) remained as an open problem, since 2009. We achieve such a characterization for a class of graphs that includes chordal graphs and internally triangulated planar graphs. For biconnected chordal graphs, our characterization leads to a polynomial time algorithm for precisely determining evc(G) and an algorithm for determining a safe strategy for guard movement in each round of the game using only evc(G) guards. Though the eternal vertex cover problem is only known to be in PSPACE in general, it follows from our new characterization that the problem is in NP for locally connected graphs, a graph class which includes all biconnected internally triangulated planar graphs. We also provide reductions establishing NP-completeness of the problem for biconnected internally triangulated planar graphs. As far as we know, this is the first NP-completeness result known for the problem for any graph class. © 2021 Elsevier B.V.

On graphs whose eternal vertex cover number and vertex cover number coincide

The main result in this paper is a new lower bound to the eternal vertex cover number (evc number) of an arbitrary graph G in terms of the size of the smallest vertex cover in G that includes all the cut vertices of G. As a consequence, we obtain a quadratic complexity algorithm for finding the evc number of any chordal graph. Another consequence is a polynomial time approximation scheme for finding the evc number of internally triangulated planar graphs, for which exact determination of evc number is known to be NP-hard (Babu et al. in Discrete Appl Math, 2021. https://doi.org/10.1016/j.dam.2021.02.004). The lower bound is proven by considering a decomposition of the graph into a collection of edge disjoint induced subgraphs, and deriving a lower bound for the evc number of the whole graph in terms of bounds obtained for the subgraphs. As another consequence of the bounding technique, we obtain a construction of a family of biconnected bipartite graphs such that for any ϵ> 0 , there exists a graph in the family such that the ratio of its evc number to the size of its minimum vertex cover exceeds 2 - ϵ. This construction is asymptotically optimal, as it is known (Klostermeyer and Mynhardt in Aust J Comb 45:235–250, 2009) that this ratio has to be strictly less than 2 for biconnected graphs. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

Journal of Combinatorial Optimization

A new lower bound for the eternal vertex cover number of graphs

We investigate the Ramsey number r(Im,Ln) which is the smallest natural number k such that every oriented graph on k vertices contains either an independent set of size m or a transitive tournament on n vertices. Continuing research by Larson and Mitchell and earlier work by Bermond we establish two new upper bounds for r(Im,L3) which are paramount in proving r(I4,L3)=15&lt;23=r(I5,L3) and r(Im,L3)=Θ(m2∕logm), respectively. We furthermore elaborate on implications of the latter on upper bounds for r(Im,Ln). © 2020 Elsevier B.V.