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

The static deployment of Virtualized Network Functions (VNFs) introduces 1) significant degradation of Quality of Service (QoS), 2) inefficiency in the network and computing resource utilization, and 3) Network Function Virtualization (NFV)-based services with insufficient scalability, optimality, and flexibility. Caching VNFs is a promising solution to satisfy the dynamic demand to deploy a variety of VNFs and to maximize the performance as well as cost effectiveness. Although the concept of Content Delivery Network (CDN) is popular for efficiently caching and distributing contents, VNF deployment does not realize the benefit of CDN-based caching approaches. The challenges to caching VNFs are 1) to cover the large variety of VNFs and their properties, including the necessity of service chaining, and 2) to achieve high acceptance ratio given the limited availability of resources. This paper proposes Function Delivery Network (FDN), which is a cluster of distributed edge hypervisors for caching VNFs over a Software-Defined Network (SDN). The deployment and quality of the network function can be significantly improved by serving them closer to the end-users from the cached VNFs. FDN introduces a new strategy called Value-based caching that considers 1) the locality of reference and performance parameters of network and edge hypervisors together and 2) a partial deployment of service chains across multiple edge hypervisors for further efficient utilization of hypervisors resources. Evaluations on different patterns of input requests confirm thatValue-based caching introduces significant improvement on both QoS and resource utilization in NFV. © 2020 Institute of Electronics, Information and Communication, Engineers, IEICE. All rights reserved.

World University root node

IEICE Transactions on Communications

FDN: Function delivery network-optimizing service chain deployment in nfv

This paper explores the power of catalytic computation when the catalytic space (c(n), the full memory for which the content needs to be restored to original content at the end of the computation) is much more than exponential in the pure space (s(n), the empty memory which does not have any access/restoration constraints). We study the following three regimes of the relation between s(n) and c(n) and explore the class in each of them. Low-end regime: We define the classes and (nondeterministic variant of) where and. Exploring the connection between computational power of one counter machines (OC) and constant pure space catalytic Turing machines, we observe that and show that. We prove that Low-end non-constant regime: Let M be an oblivious catalytic Turing machine using s(n) pure space and c(n) catalytic space such that then L(M) is regular. This strengthens the classical theorem on to the case of catalytic Turing machines.High-end regime: We show an implementation of incremental dynamic program using catalytic machines, thus showing that Knapsack problem (with n items, sum of their costs as C and the capacity of the bag as K) can be solved in pure space and catalytic space. Hence, catalytic algorithms can lead to a non-trivial saving in the pure space required for computation when K is. Our techniques include interesting generalizations of crossing sequence arguments and implementations of incremental dynamic programs using catalytic algorithms. These may be of independent interest. © 2020, Springer Nature Switzerland AG.

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

On Pure Space vs Catalytic Space

In this paper, we study the Boolean function parameters sensitivity (s), block sensitivity (bs), and alternation (alt) under specially designed affine transforms and show several applications. For a function f:F2n→{−1,1}, and A=Mx+b for M∈F2n×n and b∈F2n, the result of the transformation g is defined as ∀x∈F2n,g(x)=f(Mx+b). 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 salt(f)). By a result of Lin and Zhang (2017) [7], it follows that bs(f)≤O(salt(f)2s(f)). Thus, to settle the Sensitivity Conjecture (∀f,bs(f)≤poly(s(f))), it suffices to argue that ∀f,salt(f)≤poly(s(f)). However, we exhibit an explicit family of Boolean functions for which salt(f) is 2Ω(s(f)). Going further, we use an affine transform A, such that the corresponding function g satisfies bs(f,0n)≤s(g). We apply this in the setting of quantum communication complexity to prove that for F(x,y)=deff(x∧y), the bounded error quantum communication complexity of F with prior entanglement, Q1/3⁎(F) is Ω(bs(f,0n)). Our proof builds on ideas from Sherstov (2010) [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 ϵ, 0&lt;ϵ&lt;1, any Boolean function f that depends on all its inputs with degp(f)≤(1−ϵ)log⁡n must satisfy [Formula presented]. Here, degp(f) denotes the degree of the multilinear polynomial over Fp which agrees with f on Boolean inputs. (b) For Boolean function f such that there exists primes p and q with degq(f)≥Ω(degp(f)δ) for δ&gt;2, the deterministic communication complexity - D(F) and Q1/3⁎(F) are polynomially related. In particular, this holds when degp(f)=O(1). Thus, for this class of functions, this answers an open question (see Buhrman and de Wolf (2001) [15]) 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, alt(f)≤2s(g)+1. Using this new relation, we exhibit Boolean functions f (other than the parity function) such that s(f) is Ω(sparsity(f)) where sparsity(f) is the number of non-zero coefficients in the Fourier representation of f. This family of Boolean functions also rule out a potential approach to settle the XOR Log-Rank conjecture via the recently settled Sensitivity conjecture (Hao Huang (2019) [5]). © 2020 Elsevier B.V.

Fulltext

Theoretical Computer Science

Sensitivity, affine transforms and quantum communication complexity

Deep Neural Networks (DNN) are very effective in high performance applications such as computer vision, natural language processing and speech recognition. However, these networks are vulnerable to adversarial attacks that infuses perturbations in the input data which are imperceptible to human eyes. In this paper, we propose a novel decision-based targeted adversarial attack algorithm which exposes the vulnerability of the underlying DNN when implemented on a resource constrained computing edge. Experimental results show that the proposed model performs 4 seconds(s) faster on an average, in a single perturbed image generation than the state of the art RED-attack, while consuming 15% less time for the entire dataset. © 2020 IEEE.

Department of Data Science

IEEE Workshop on Signal Processing Systems, SiPS: Design and Implementation

Fast and Efficient Decision-Based Attack for Deep Neural Network on Edge

We study four problems namely, Campbell's source coding problem, Arikan's guessing problem, Huieihel et al.'s memoryless guessing problem, and Bunte and Lapidoth's task partitioning problem. We observe a close relationship among these problems. In all these problems, the objective is to minimize moments of some functions of random variables, and Rényi entropy and Sundaresan's divergence arise as optimal solutions. This motivates us to establish a connection among these four problems. In this paper, we study a more general problem and show that Rényi and Shannon entropies arise as its solution. We show that the problems on source coding, guessing and task partitioning are particular instances of this general optimization problem, and derive the lower bounds using this framework. We also refine some known results and present new results for mismatched version of these problems using a unified approach. We strongly feel that this generalization would, in addition to help in understanding the similarities and distinctiveness of these problems, also help to solve any new problem that falls in this framework.

Deep AI

A Unified Framework for Problems on Guessing, Source Coding and Task Partitioning

A sequence urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0001 contains a pattern urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0002, that is, a permutations of [k], iff there are indices i1 &lt; … &lt; ik, such that f(ix) &gt; f(iy) whenever π(x) &gt; π(y). Otherwise, f is π-free. We study the property testing problem of distinguishing, for a fixed π, between π-free sequences and the sequences which differ from any π-free sequence in more than ϵ n places. Our main findings are as follows: (1) For monotone patterns, that is, π = (k,k − 1,…,1) and π = (1,2,…,k), there exists a nonadaptive one-sided error ϵ-test of urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0003 query complexity. For any other π, any nonadaptive one-sided error test requires urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0004 queries. The latter lower-bound is tight for π = (1,3,2). For specific urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0005 it can be strengthened to Ω(n1 − 2/(k + 1)). The general case upper-bound is O(ϵ−1/kn1 − 1/k). (2) For adaptive testing the situation is quite different. In particular, for any urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0006 there exists an adaptive ϵ-tester of urn:x-wiley:rsa:media:rsa20840:rsa20840-math-0007 query complexity.

Testing for forbidden order patterns in an array

Computing Herbrand equivalences of terms in data flow frameworks is well studied in program analysis. While algorithms use iterative fix-point computation on some abstract lattice of expressions relevant to the flow graph, the definition of Herbrand equivalences is based on an equivalence over all program paths formulation, on the (infinite) set of all expressions. The aim of this paper is to develop a lattice theoretic fix-point formulation of Herbrand equivalence on a concrete lattice defined over the set of all terms constructible from variables, constants and operators of a program. This new formulation makes explicit the underlying lattice framework as well as the monotone function involved in computing Herbrand equivalences. We introduce the notion of Herbrand congruence and define an (infinite) concrete lattice of Herbrand congruences. Herbrand equivalence is defined as the maximum fix-point of a composite transfer function defined over an appropriate product lattice of the above concrete lattice. We then re-formulate the traditional meet over all paths definition in our lattice theoretic framework. and prove that the maximum fix-point (MFP) and the meet-over-all-paths (MOP) formulations coincide as expected. © 2019, Springer-Verlag GmbH Germany, part of Springer Nature.

A fix-point characterization of herbrand equivalence of expressions in data flow frameworks

The well-known SENSITIVITY CONJECTURE regarding combinatorial complexity measures on Boolean functions states that for any Boolean function f:{0,1} n →{0,1}, block sensitivity of f is polynomially related to sensitivity of f (denoted by s(f)). From the complexity theory side, the XOR LOG-RANK CONJECTURE states that for any Boolean function, f:{0,1} n →{0,1} the communication complexity of a related function f ⊕ :{0,1} n ×{0,1} n →{0,1} (defined as f ⊕ (x,y)=f(x⊕y)) is bounded by polynomial in logarithm of the sparsity of f (the number of non-zero Fourier coefficients for f, denoted by sparsity(f)). Both the conjectures play a central role in the domains in which they are studied. A recent result of Lin and Zhang (2017) implies that to confirm the above two conjectures it suffices to upper bound alternation of f (denoted by alt(f)) for all Boolean functions f by polynomial in s(f) and logarithm of sparsity(f), respectively. In this context, we show the following results: • We show that there exists a family of Boolean functions for which alt(f) is at least exponential in s(f) and alt(f) is at least exponential in log⁡sparsity(f). En route to the proof, we also show an exponential gap between alt(f) and the decision tree complexity of f, which might be of independent interest. • As our main result, we show that, despite the above exponential gap between alt(f) and log⁡sparsity(f), the XOR LOG-RANK CONJECTURE is true for functions with the alternation upper bounded by poly(log⁡n). It is easy to observe that the SENSITIVITY CONJECTURE is also true for this class of functions. • The starting point for the above result is the observation (derived from Lin and Zhang (2017)) that for any Boolean function f, deg(f)≤alt(f)deg 2 (f)deg m (f) where deg(f), deg 2 (f) and deg m (f) are the degrees of f over R, F 2 and Z m respectively. We give three further applications of this bound: (1) We show that for Boolean functions f of constant alternation have deg 2 (f)=Ω(log⁡n). (2) Moreover, these functions also have high sparsity (exp⁡(Ω(deg(f))), thus partially answering a question of Kulkarni and Santha (2013). (3) We observe that our relation upper bounding real degree also improves the upper bound for influence to deg 2 (f) 2 ⋅alt(f) improving Guo and Komargodski (2017). © 2018 Elsevier B.V.

Alternation, sparsity and sensitivity: Bounds and exponential gaps

Runtime verification employs dedicated hardware or software monitors to check whether program properties hold at runtime. However, these monitors often incur high area and performance overheads depending on whether they are implemented in hardware or software. In this work, we propose DHOOM, an architectural framework for runtime monitoring of program assertions, which exploits the combination of a reconfigurable fabric present alongside a processor core with the vestigial on-chip Design-for-Debug hardware. This combination of hardware features allows DHOOM to minimize the overall performance overhead of runtime verification, even when subject to a given area constraint. We present an algorithm for dynamically selecting an effective subset of assertion monitors that can be accommodated in the available programmable fabric, while instrumenting the remaining assertions in software. We show that our proposed strategy, while respecting area constraints, reduces the performance overhead of runtime verification by up to 32% when compared with a baseline of software-only monitors. © 2019 Association for Computing Machinery.

Proceedings - Design Automation Conference

DHOOM: Reusing design-for-debug hardware for online monitoring

Dynamic Adaptive Streaming over HTTP (DASH) has become the standard choice for live events and on-demand video services. In fact, by performing bitrate adaptation at the client side, DASH operates to deliver the highest possible Quality of Experience (QoE) under given network conditions. In cellular networks, in particular, video streaming services are affected by mobility and cell load variation. In this context, DASH video clients continually adapt the streaming quality to cope with channel variability. However, since they operate in a greedy manner, adaptive video clients can overload cellular network resources, degrading the QoE of other users and suffer persistent bitrate oscillations. In this paper, we tackle this problem using a new eNB scheduler, named Shadow-Enforcer, which ensures minimal number of quality switches as well as efficient and fair utilization of network resources. Our scheduler works well under dynamic scenarios and mobility and requires minimal information, i.e., just the set of video bitrates supported by DASH video clients. It consists of the cascade of a virtual scheduler, Shadow and the actual scheduler, Enforcer, piloted by the virtual one. Extensive simulations demonstrate the efficiency, fairness and the smooth response to channel variations of the proposed solution.