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

Video streaming over cellular network has become extremely popular in 4G and will be an integral part of future cellular networks. While most modern-day video clients continually adapt quality of video streams, they neither coordinate with network elements nor among each other. Consequently, a streaming client may quickly overload the cellular network, leading to poor Quality of Experience (QoE) for users in the network. Motivated by this problem, we present D-VIEWS-a scheduling paradigm that assures video bitrate stability of adaptive video streams while ensuring better system utilization. D-VIEWS only needs to be aware of the set of video bitrates and requires no changes to streaming clients and other network functions. Through simulations, we also study the performance of proportional fairness scheduler and D-VIEWS in the presence of user arrival and departure events. © 2004-2012 IEEE.

World University root node

Fulltext

IEEE Transactions on Network and Service Management

Enforcing Bitrate-Stability for Adaptive Streaming Traffic in Cellular Networks

Given a graph G=(V,E) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai–Roy–Vitaver Theorem that every properly coloured graph contains a colourful path on χ(G) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on χ(G) vertices and prove its correctness when the girth of G is at least χ(G). Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function f such that if χ(G)≥f(k), then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G. © 2018 Elsevier B.V.

Discrete Applied Mathematics

On induced colourful paths in triangle-free graphs

In vertex deletion problems on graphs, the task is to find a set of minimum number of vertices whose deletion results in a graph with some specific property. The class of vertex deletion problems contains several classical optimization problems, and has been studied extensively in algorithm design. Recently, there was a study on vertex deletion problems on split graphs. One of the results shown was that transforming a split graph into a block graph and 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 these problems in the realm of parameterized complexity with respect to the number of vertex deletions k as parameter. These problems are “implicit” 4-Hitting Set, and thus admit an algorithm with running time, a kernel with vertices, and a 4-approximation algorithm. In this paper, we exploit the structure of the input graph to obtain a kernel for SBVD with vertices and FPT algorithms for SBVD and STVD with running times and. © 2019, Springer Nature Switzerland AG.

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

Vertex Deletion on Split Graphs: Beyond 4-Hitting Set

Energy management is a critical challenge in multi-core processors due to continuous technology scaling. Previous methods have mostly focused on the energy minimization of the processor cores. However, energy overhead of the off-chip voltage regulator (VR) has recently shown to be a non-trivial part of the total energy consumption and has been previously overlooked. In this paper, we propose an overall energy optimization method for the system that minimizes both per-core energy consumption and VR energy consumption using dynamic voltage frequency scaling (DVFS) and VR phase scaling by solving a comprehensive convex model. In order to improve the accuracy of the task latency model, a new task model considering both computation and memory access of the task is also developed. Furthermore, for better scalability and lower on-line overhead, we decompose our proposed convex method into two stages: an off-line stage and an on-line stage. During the off-line stage, we explore the convex model by assuming different numbers of active phases of the VR, various workload pressures and workload characteristics to collect the optimal frequency assignments under different scenarios. During the online stage, the specific frequency assignment for cores and optimal active phase number of the VR are selected and applied based on the actual workload pressure and its characteristics running on the cores. Experiments on real benchmarks show that when compared with state-of-the-art approaches, which are oblivious to VR overheads and exploit slack time to achieve energy minimization, our method can achieve a significant energy saving of up to 22.4% with negligible on-line overhead. IEEE

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

Energy Minimization for Multi-core Platforms through DVFS and VR Phase Scaling With Comprehensive Convex Model

Aggressive technology scaling enabled very high integration density. Unfortunately, it also led to issues such as process variation, increased power density and consequently rising chip temperature resulting in accelerated device aging and poor lifetime reliability of different components in a manycore system. Moreover, thermal and power limitations let only a fraction of the chip function at full speed; the rest is the dark silicon. Most of the lifetime reliability enhancement solutions for the multi-/manycore systems in the literature are heuristic-based, while some use standard compute-intensive methods to solve the optimization problem making them not scale well with the manycore size. The heuristic-based solutions are formulated to search through the design space of a fine granularity making it huge, limiting their scalability. Also, these approaches do not account for the impact of different applications' execution behavior on the aging of the underlying cores, and their performance requirement distribution across the cores to their advantage. In this paper, we present our resource management strategies towards building scalable lifetime reliability enhancement solutions for dark silicon manycore systems. The first technique, Hierarchical Mapping approach (HiMap), maps a periodic workload employing a block-based hierarchical method that leverages dark cores for thermal mitigation. The second approach, LifeGuard, uses reinforcement learning to learn the applications' aging behavior, and is aware of the performance requirement pattern onto the core frequencies. It maps randomly arriving requests and is scalable to the number of applications and the size of a manycore. © 2019 IEEE.

2019 IEEE 25th International Symposium on On-Line Testing and Robust System Design, IOLTS 2019

Towards Scalable Lifetime Reliability Management for Dark Silicon Manycore Systems

In this paper, we develop an analytical framework to compute the Quality-of-Experience (QoE) metrics of video streaming in wireless networks. Our framework takes into account the system dynamics that arises due to the arrival and departure of flows. We also consider the possibility of users abandoning the system on account of poor QoE. Considering the coexistence of multiple services such as video streaming and elastic flows, we use a Markov chain based analysis to compute the user QoE metrics: probability of starvation, prefetching delay, average video quality and bitrate switching. Our simulation results validate the accuracy of our model and describe the impact of scheduler at eNB on the QoE metrics. © 2019 IEEE.

IEEE Wireless Communications and Networking Conference, WCNC

Analysis of QoE for Adaptive Video Streaming over Wireless Networks with User Abandonment Behavior

A graph is called a split graph if its vertex set can be partitioned into a clique and an independent set. Split graphs have rich mathematical structure and interesting algorithmic properties making it one of the most well-studied special graph classes. In the Split Vertex Deletion(SVD) problem, given a graph and a positive integer k, the objective is to test whether there exists a subset of at most k vertices whose deletion results in a split graph. In this paper, we design a kernel for this problem with vertices, improving upon the previous cubic bound known. Also, by giving a simple reduction from the Vertex Cover problem, we establish that SVD does not admit a kernel with edges, for any, unless. © 2019, Springer Nature Switzerland AG.

Quadratic Vertex Kernel for Split Vertex Deletion

In this paper, we construct explicit families of quantum error correcting codes based on cyclic codes. But for a crucial theoretical idea that we introduce here, namely working with a modified symplectic form as the basis of Weyl commutation, these codes would not have been possible - under the standard symplectic form, there are Galois theoretic no-go theorems on cyclic codes [7], [Corollary IV.5, page 651], [6], [Corollary 5.16, page 51] of certain lengths. More importantly, we circumvent the above no-go theorems without disturbing the one crucial property that cyclic codes have - efficient decoding algorithms. Recall that for general codes, efficient decoding algorithms do not exist if some widely believed complexity theoretic assumptions are true hence this is a crucial property to have. Cyclicity is a basis dependent property and for codes that we construct, is only evident in the modified symplectic setting. If we were to recast this code using the standard symplectic form, there would be a basis change on the underlying vector space that disturbs cyclicity. Hence, this change of perspective that we have here is crucial not only in the construction, where we had to circumvent the no-go theorems that we mentioned above, but also in the design of efficient decoding algorithm. Theoretically our result is also tight: we have a complete characterization (Theorem 6) of the codes that we construct here. © 2019 IEEE.

IEEE International Symposium on Information Theory - Proceedings

Stabilizer codes from modified symplectic forms

In this paper, we study the Boolean function parameters sensitivity ((Formula Presented) ), block sensitivity ((Formula Presented) ), and alternation ((Formula Presented) ) under specially designed affine transforms and show several applications. For a function (Formula Presented), and (Formula Presented) for (Formula Presented) and (Formula Presented), the result of the transformation g is defined as (Formula Presented). As a warm up, we study alternation under linear shifts (when M is restricted to be the identity matrix) called the shift invariant alternation (the smallest alternation that can be achieved for the Boolean function f by shifts, denoted by (Formula Presented) ). By a result of Lin and Zhang [12], it follows that (Formula Presented). Thus, to settle the Sensitivity Conjecture ((Formula Presented) ), it suffices to argue that (Formula Presented). However, we exhibit an explicit family of Boolean functions for which (Formula Presented) is (Formula Presented). Going further, we use an affine transform A, such that the corresponding function g satisfies (Formula Presented), to prove that for (Formula Presented), the bounded error quantum communication complexity of F with prior entanglement, (Formula Presented) is (Formula Presented). Our proof builds on ideas from Sherstov [17] where we use specific properties of the above affine transformation. Using this, we show the following. (a)For a fixed prime p and an (Formula Presented), any Boolean function f that depends on all its inputs with (Formula Presented) must satisfy (Formula Presented). Here, (Formula Presented) denotes the degree of the multilinear polynomial over (Formula Presented) which agrees with f on Boolean inputs.(b)For Boolean function f such that there exists primes p and q with (Formula Presented) for (Formula Presented), the deterministic communication complexity - (Formula Presented) and (Formula Presented) are polynomially related. In particular, this holds when (Formula Presented). Thus, for this class of functions, this answers an open question (see [2]) about the relation between the two measures. Restricting back to the linear setting, we construct linear transformation A, such that the corresponding function g satisfies, (Formula Presented). Using this new relation, we exhibit Boolean functions f (other than the parity function) such that (Formula Presented) is (Formula Presented) where (Formula Presented) is the number of non-zero coefficients in the Fourier representation of f. © Springer Nature Switzerland AG 2019.

Sensitivity, Affine Transforms and Quantum Communication Complexity

The eternal vertex cover problem is a variant of the classical vertex cover problem where a set of guards on the vertices have to be dynamically reconfigured from one vertex cover to another in every round of an attacker-defender game. The minimum number of guards required to protect a graph from an infinite sequence of attacks is the eternal vertex cover number (evc) of the graph. It is known that, given a graph G and an integer k, checking whether (G)≤k is NP-Hard. However, for any graph G, (Formula presentd), where mvc(G) is the minimum vertex cover number of G. Precise value of eternal vertex cover number is known only for certain very basic graph classes like trees, cycles and grids. Though a characterization is known for graphs for which evc(G) = 2 mvc(G), a characterization of graphs for which evc(G) = mvc(G) remained open. Here, we achieve such a characterization for a class of graphs that includes chordal graphs and internally triangulated planar graphs. For some graph classes including biconnected chordal graphs, our characterization leads to a polynomial time algorithm to precisely determine evc(G) and to determine a safe strategy of guard movement in each round of the game with evc(G) guards. © Springer Nature Switzerland AG 2019.