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

We give an N · log N · 2O(log*N) time algorithm to multiply two N-bit integers that uses modular arithmetic for intermediate computations instead of arithmetic over complex numbers as in Fürer's algorithm, which also has the same and so far the best known complexity. The previous best algorithm using modular arithmetic (by Schönhage and Strassen) has complexity O(N · log N · log log N). The advantage of using modular arithmetic as opposed to complex number arithmetic is that we can completely evade the task of bounding the truncation error due to finite approximations of complex numbers, which makes the analysis relatively simple. Our algorithm is based upon Fürer's algorithm, but uses fast Fourier transform over multivariate polynomials along with an estimate of the least prime in an arithmetic progression to achieve this improvement in the modular setting. It can also be viewed as a p-adic version of Fürer's algorithm. © 2013 Society for Industrial and Applied Mathematics.

World University root node

Fulltext

SIAM Journal on Computing

Fast integer multiplication using modular arithmetic

Energy minimization is a critical issue and challenge when considering the cyclic dependency of leakage power and temperature as IC technology reaches deep sub-micron level. In this paper, we present an analytical method to calculate the energy consumption efficiently and effectively for a given voltage schedule on a multi-core platform, with the leakage/temperature dependency taken into consideration. Our experiments show that the proposed method can achieve a speedup of 15 times compared with the numerical method, with a relative error of no more than 1.5%. © 2013 IEEE.

Proceedings of the International Symposium on Low Power Electronics and Design

An analytical solution for multi-core energy calculation with consideration of leakage and temperature dependency

The internal state of complex modern processors often needs to be dumped out frequently during post-silicon validation. Since the last level cache (considered L2 in this paper) holds most of the state, the volume of data dumped and the transfer time are dominated by the L2 cache. The limited bandwidth to transfer data off-chip coupled with the large size of L2 cache results in stalling the processor for long durations when dumping the cache contents off-chip. To alleviate this, we propose to transfer only those cache lines that were updated since the previous dump. Since maintaining a bit-vector with a separate bit to track the status of individual cache lines is expensive, we propose 2 methods: (i) where a bit tracks multiple cache lines and (ii) an Interval Table which stores only the starting and ending addresses of continuous runs of updated cache lines. Both methods require significantly lesser space compared to a bit-vector, and allow the designer to choose the amount of space to allocate for this design-for-debug (DFD) feature. The impact of reducing storage space is that some non-updated cache lines are dumped too. We attempt to minimize such overheads. Further, the Interval Table is independent of the cache size which makes it ideal for large caches. Through experimentation, we also determine the break-even point below which a t-lines/bit bit-vector is beneficial compared to an Interval Table. © 2013 EDAA.

Proceedings -Design, Automation and Test in Europe, DATE

Space sensitive cache dumping for post-silicon validation

The product dimension of a graph G is defined as the minimum natural number l such that G is an induced subgraph of a direct product of l complete graphs. In this paper we study the product dimension of forests, bounded treewidth graphs and k-degenerate graphs. We show that every forest on n vertices has product dimension at most 1.441 log n + 3. This improves the best known upper bound of 3 log n for the same due to Poljak and Pultr. The technique used in arriving at the above bound is extended and combined with a well-known result on the existence of orthogonal Latin squares to show that every graph on n vertices with treewidth at most t has product dimension at most (t+2)(log n+1). We also show that every k-degenerate graph on n vertices has product dimension at most ⌈5.545k log n⌉+1. This improves the upper bound of 32k log n for the same by Eaton and Rödl.

Electronic Journal of Combinatorics

Product dimension of forests and bounded treewidth graphs

A graph is k-chordal if it has no induced cycle of length greater than k. We give a new characterization of k-chordal graphs that generalizes the well-known characterization of chordal graphs by Dirac in terms of simplicial vertices and simplicial orderings. © 2013 Elsevier B.V. All rights reserved.

Discrete Mathematics

A Dirac-type characterization of k-chordal graphs

Given a graph G and an odd cycle transversal T, we describe an elegant O* (2|T|) algorithm for determining whether G has a smaller odd cycle transversal that is disjoint from T. We believe that our algorithm, based on a reduction to VERTEX Cover, is conceptually simpler than the known algorithms for the problem and refines the understanding of the relationship between ODD CYCLE TRANSVERSAL and VERTEX COVER. © 2013 Elsevierc B.V. All rights reserved.

Information Processing Letters

Another disjoint compression algorithm for odd cycle transversal

Given a point set P and a class of geometric objects, is a geometric graph with vertex set P such that any two vertices p and q are adjacent if and only if there is some C ∈ C containing both p and q but no other points from P. We study G∇(P) graphs where ∇ is the class of downward equilateral triangles (ie. equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-Θ6 graphs and TD-Delaunay graphs. The main result in our paper is that for point sets P in general position, G ∇(P) always contains a matching of size at least ⌈n - 2/3⌉ and this bound cannot be improved above ⌈n - 1/3⌉. We also give some structural properties of GStar of David(P) graphs, where Star of David is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of GStar of David(P) is simply a path. Through the equivalence of GStar of David(P) graphs with Θ6 graphs, we also deduce that any Θ6 graph can have at most 5n - 11 edges, for point sets in general position. © 2013 Springer-Verlag.

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

Fixed-orientation equilateral triangle matching of point sets

We consider the (r, l)-Partization problem of finding a set of at most k vertices whose deletion results in a graph that can be partitioned into r independent sets and l cliques. Restricted to perfect graphs and split graphs, we describe sequacious fixed-parameter tractability results for (r, 0)-Partization, parameterized by k and r. For (r, l)-Partization where r+l = 2, we describe an O*(2k) algorithm for perfect graphs. We then study the parameterized complexity hardness of a generalization of the Above Guarantee Vertex Cover by a reduction from (r, l)-Partization.

Journal of Graph Algorithms and Applications

Parameterized algorithms for (r, l)-Partization

A rainbow colouring of a connected graph G is a colouring of the edges of G such that every pair of vertices in G is connected by at least one path in which no two edges are coloured the same. The minimum number of colours required to rainbow colour G is called its rainbow connection number. Chakraborty, Fischer, Matsliah and Yuster have shown that it is NP-hard to compute the rainbow connection number of graphs [J. Comb. Optim., 2011]. Basavaraju, Chandran, Rajendraprasad and Ramaswamy have reported an (r + 3)-factor approximation algorithm to rainbow colour any graph of radius r [Graphs and Combinatorics, 2012]. In this article, we use a result of Guruswami, Hästad and Sudan on the NP-hardness of colouring a 2-colourable 4-uniform hypergraph using constantly many colours [SIAM J. Comput., 2002] to show that for every positive integer κ, it is NP-hard to distinguish between graphs with rainbow connection number 2κ + 2 and 4κ + 2. This, in turn, implies that there cannot exist a polynomial time algorithm to rainbow colour graphs with less than twice the optimum number of colours, unless P = NP. The authors have earlier shown that the rainbow connection number problem remains NPhard even when restricted to the class of chordal graphs, though in this case a 4-factor approximation algorithm is available [COCOON, 2012]. In this article, we improve upon the 4-factor approximation algorithm to design a linear-time algorithm that can rainbow colour a chordal graph G using at most 3/2 times the minimum number of colours if G is bridgeless and at most 5/2 times the minimum number of colours otherwise. Finally we show that the rainbow connection number of bridgeless chordal graphs cannot be polynomial-time approximated to a factor less than 5/4, unless P = NP. © L. Sunil Chandran and Deepak Rajendraprasad.

Leibniz International Proceedings in Informatics, LIPIcs

Inapproximability of rainbow colouring

In this document, we are primarily interested in computing the probabilities of various types of dependencies that can occur in a multi-cell infrastructure network.