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

In the Cycle Packing problem, we are given an undirected graph G, a positive integer r, and the task is to check whether there exist r vertex-disjoint cycles. In this paper, we study Cycle Packing with respect to a structural parameter, namely, distance to proper interval graphs (indifference graphs). In particular, we show that Cycle Packing is fixed-parameter tractable (FPT) when parameterized by t, the size of a proper interval deletion set. For this purpose, we design an algorithm with O(2 O ( t log t )nO ( 1 )) running time. Bodlaender et al. (Theor Comput Sci 511:117–136, 2013) studied several structural parameterizations for Cycle Packing and our FPT algorithm fills a gap in their ecology of parameterizations. We combine color coding, greedy strategy and dynamic programming based on structural properties of proper interval graphs in a non-trivial fashion to obtain the FPT algorithm. Our belief is that this approach is quite general and can be useful in solving many other problems with the same parameterization. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.

World University root node

Algorithmica

The Parameterized Complexity of Cycle Packing: Indifference is Not an Issue

Device scaling to subdeca nanometer has pushed device aging as a primary design concern. In manycore systems, inevitable process variation further adds to delay degradation and, coupled with the scalability issues in manycores, makes aging management, while meeting performance demands, a complex problem. LifeGuard is a performance-centric reinforcement learning-based task mapping strategy that leverages the different impact of applications on aging for improving system health. Experimental results, comparing Life- Guard with two state-of-the-art aging optimizing techniques, on a 256-core system, showed that LifeGuard led to improved health for, respectively, 57% and 74% of the cores, and also an enhanced aggregate core frequency. © 2019 Association for Computing Machinery.

Proceedings - Design Automation Conference

LifeGuard: A reinforcement learning-based task mapping strategy for performance-centric aging management

Memory-safety attacks have been one of the most critical threats against computing systems. Although a wide-range of defense techniques have been developed against these attacks, the existing mitigation strategies have several limitations. In particular, most of the existing mitigation approaches are based on aborting or restarting the victim program when a memory-safety attack is detected, thus making the system unavailable. This might not be acceptable in systems with stringent timing constraints, such as cyber-physical systems (CPS), since the system unavailability leaves the control system in an unsafe state. To address this problem, we propose CIMA -- a resilient and light-weight mitigation technique that prevents invalid memory accesses at runtime. CIMA manipulates the compiler-generated control flow graph to automatically detect and bypass unsafe memory accesses at runtime, thereby mitigating memory-safety attacks along the process. An appealing feature of CIMA is that it also ensures system availability and resilience of the CPS even under the presence of memory-safety attacks. To this end, we design our experimental setup based on a realistic Secure Water Treatment (SWaT) and Secure Urban Transportation System (SecUTS) testbeds and evaluate the effectiveness and the efficiency of our approach. The experimental results reveal that CIMA handles memory-safety attacks effectively with low overhead. Moreover, it meets the real-time constraints and physical-state resiliency of the CPS under test.

Taming the War in Memory: A Resilient Mitigation Strategy Against Memory Safety Attacks in CPS

In the CYCLE PACKING problem, we are given an undirected graph G, a positive integer r, and the task is to check whether there exist r vertex-disjoint cycles. In this paper, we study CYCLE PACKING with respect to a structural parameter, namely, distance to proper interval graphs (indifference graphs). In particular, we show that CYCLE PACKING is fixed-parameter tractable (FPT) when parameterized by t, the size of a proper interval deletion set. For this purpose, we design an algorithm with O(2O(tlogt)nO(1))<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><msup><mn>2</mn><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mi>t</mi><mi>log</mi><mo>⁡</mo><mi>t</mi><mo stretchy="false">)</mo></mrow></msup><msup><mi>n</mi><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi class="MJX-tex-caligraphic" mathvariant="script">O</mi></mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup><mo stretchy="false">)</mo></math>&nbsp;running time. Several structural parameterizations for CYCLE PACKING have been studied in the literature and our FPT algorithm fills a gap in the ecology of such parameterizations. We combine color coding, greedy strategy and dynamic programming based on structural properties of proper interval graphs in a non-trivial fashion to obtain the FPT algorithm.

Latin American Symposium on Theoretical Informatics

The Parameterized Complexity of Cycle Packing: Indifference is Not an Issue

Edge-intersection graphs of paths on a grid (or EPG graphs) are graphs whose vertices can be represented as simple paths on a rectangular grid such that two vertices are adjacent in the graph if and only if the corresponding paths share at least one edge of the grid. For two boundary points p and q on two adjacent boundaries of a rectangular grid G, we call the unique single-bend path connecting p and q in G using no other boundary point of G as the path generated by (p,q). A path in G is called boundary-generated, if it is generated by some pair of points on two adjacent boundaries of G. In this article, we study the edge-intersection graphs of boundary-generated paths on a grid or ∂EPG graphs. The motivation for studying these graphs comes from problems in the context of circuit layout. We show that ∂EPG graphs can be covered by two collections of vertex-disjoint co-bipartite chain graphs. This leads us to a linear-time testable characterization of ∂EPG trees and also an almost tight upper bound on the equivalence covering number of general ∂EPG graphs. We also study the cases of two-sided ∂EPG and three-sided ∂EPG graphs, which are respectively, the subclasses of ∂EPG graphs obtained when all the boundary-vertex pairs which generate the paths are restricted to lie on at most two or three boundaries of the grid. For the former case, we give a complete characterization. © 2017 Elsevier B.V.

Discrete Applied Mathematics

Edge-intersection graphs of boundary-generated paths in a grid

Post-Silicon Validation and Debug

Debug data reduction techniques

We consider the problem of distributed scheduling in wireless communication networks where heterogeneously delayed queue lengths and channel states of all links are available at all the transmitters. In an earlier work (by Reddy et al. in Queueing Systems, 2012), a throughput-optimal scheduling policy (which we refer to henceforth as the R policy) for this setting was proposed. We study the R policy, and examine its two drawbacks — (i) its huge computational complexity, and (ii) its non-optimal average per-packet queueing delay. We show that the R policy unnecessarily constrains itself to work with information that is more delayed than that afforded by the system. We propose a new distributed scheduling policy that fully exploits the common state information available to all transmitters, thereby greatly improving upon the computational complexity and the delay performance relative to those of the R policy. We also establish the throughput optimality of our policy analytically. We evaluate the performance of the proposed policy and validate our analytical results through extensive numerical simulation. Thus, our work enlarges the ambit of networks for which throughput-optimal scheduling is practicable. © 2018 Elsevier B.V.

Performance Evaluation

Reduced-complexity delay-efficient throughput-optimal distributed scheduling with heterogeneously delayed network-state information

For a Boolean function (Formula Presented) computed by a circuit C over a finite basis (Formula Presented), the energy complexity of C (denoted by (Formula Presented)) is the maximum over all inputs (Formula Presented) the numbers of gates of the circuit C (excluding the inputs) that output a one. Energy complexity of a Boolean function over a finite basis (Formula Presented) denoted by where C is a circuit over (Formula Presented) computing f. We study the case when (Formula Presented), 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 (Formula Presented) for a small (Formula Presented) (which we observe is improvable to (Formula Presented)). We show several new results and connections between energy complexity and other well-studied parameters of Boolean functions. For all Boolean functions f, (Formula Presented) where (Formula Presented) is the optimal decision tree depth of f.We define a parameter positive sensitivity (denoted by (Formula Presented)), a quantity that is smaller than sensitivity and defined in a similar way, and show that for any Boolean circuit C computing a Boolean function f, (Formula Presented).Restricting the above notion of energy complexity to Boolean formulas, denoted (Formula Presented), we show that (Formula Presented) where L(f) is the minimum size of a formula computing f. We next prove lower bounds on energy for explicit functions. In this direction, we show that for the perfect matching function on an input graph of n edges, any Boolean circuit with bounded fan-in must have energy (Formula Presented). We show that any unbounded fan-in circuit of depth 3 computing the parity on n variables must have energy is (Formula Presented). © 2018, Springer International Publishing AG, part of Springer Nature.

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

New bounds for energy complexity of boolean functions

For a collection F of graphs, given a graph G and an integer k, the F -Contraction problem asks whether we can contract k edges in G to obtain a graph in F. F -Contraction is well studied and known to be C-complete for several classes F. Heggerners et al. [Algorithmica (2014)] were the first to explicitly study contraction problems in the realm of parameterized complexity. They presented FPT algorithms for Tree-Contraction and Path-Contraction. In this paper, we study contraction to a class larger than trees, namely, cactus graphs. We present an FPT algorithm for Cactus-Contraction that runs in (Formula Presented) time for some constant c. © 2018, Springer International Publishing AG, part of Springer Nature.

An FPT algorithm for contraction to cactus

We study a stochastic game framework with dynamic set of players, for modeling and analyzing their computational investment strategies in distributed computing. Players obtain a certain reward for solving the problem or for providing their computational resources, while incur a certain cost based on the invested time and computational power. We first study a scenario where the reward is offered for solving the problem, such as in blockchain mining. We show that, in Markov perfect equilibrium, players with cost parameters exceeding a certain threshold, do not invest; while those with cost parameters less than this threshold, invest maximal power. Here, players need not know the system state. We then consider a scenario where the reward is offered for contributing to the computational power of a common central entity, such as in volunteer computing. Here, in Markov perfect equilibrium, only players with cost parameters in a relatively low range in a given state, invest. For the case where players are homogeneous, they invest proportionally to the 'reward to cost' ratio. For both the scenarios, we study the effects of players' arrival and departure rates on their utilities using simulations and provide additional insights.