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

This article studies the efficacy of the Metropolis algorithm for the minimum-weight codeword problem. The input is a linear code C given by its generator matrix and our task is to compute a nonzero codeword in the code C of least weight. In particular, we study the Metropolis algorithm on two possible search spaces for the problem: 1) the codeword space and 2) the generator space. The former is the space of all codewords of the input code and is the most natural one to use and hence has been used in previous work on this problem. The latter is the space of all generator matrices of the input code and is studied for the first time in this article. In this article, we show that for an appropriately chosen temperature parameter the Metropolis algorithm mixes rapidly when either of the search spaces mentioned above are used. Experimentally, we demonstrate that the Metropolis algorithm performs favorably when compared to previous attempts. When using the generator space, the Metropolis algorithm is able to outperform the previous algorithms in most of the cases. We have also provided both theoretical and experimental justification to show why the generator space is a worthwhile search space to use for this problem. © 1997-2012 IEEE.

World University root node

Department of Computer Science and Engineering

IEEE Transactions on Evolutionary Computation

Efficacy of the Metropolis Algorithm for the Minimum-Weight Codeword Problem Using Codeword and Generator Search Spaces

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

Cryptographic primitives need high-speed implementations that are also resistant to side channel attacks. The absolute control over instructions and registers that such implementations demand makes assembly language programming a necessity. In this article, we describe Verse, a typed low-level language embedded in Coq designed specifically to generate assembly language programs for cryptographic primitives. Despite being a low-level language, the programming experience is markedly high-level: • The type system of Verse is rich enough to even prevent errors in array indexing and endian conversion. • Being embedded in Coq, we have at our disposal Gallina, the underlying functional programming language, as a macro assembler for code generation, and Ltac, the tactic language, as an automation tool for proof obligations inherent to our type system. We also provide a generic framework to formulate semantic aspects of Verse. This framework has value beyond providing an interpretation of Verse in Coq. We demonstrate this versatility by using it to localise uninitialised/clobbered variable use, and arithmetic overflows. © 2018 Association for Computing Machinery.

ACM International Conference Proceeding Series

Verse: An EDSL for cryptographic primitives

Using the theory of monoids and monoid actions, we give a unified framework that handles three common pointer manipulation tasks, namely, data serialisation, deserialisation, and memory allocation. Our main theoretical contribution is the formulation of the notion of a twisted functor, a generalisation of the semi-direct product construction for monoids. We show that semi-direct products and twisted functors are particularly well suited as an abstraction for many pointer manipulation tasks. We describe the implementation of these abstractions in the context of a cryptographic library for Haskell. Twisted functors allow us to abstract all pointer arithmetic and size calculations into a few lines of code, significantly reducing the opportunities for buffer overflows. Copyright is held by the owner/author(s).

Haskell 2016 - Proceedings of the 9th International Symposium on Haskell, co-located with ICFP 2016

How to twist pointers without breaking them

We study the performance of the Metropolis algorithm for the problem of finding a code word of weight less than or equal to M, given a generator matrix of an [n; κ]-binary linear code. The algorithm uses the set Sκ of all κ × κ invertible matrices as its search space where two elements are considered adjacent if one can be obtained from the other via an elementary row operation (i.e by adding one row to another or by swapping two rows.) We prove that the Markov chains associated with the Metropolis algorithm mix rapidly for suitable choices of the temperature parameter T. We ran the Metropolis algorithm for a number of codes and found that the algorithm performed very well in comparison to previously known experimental results. © 2014 ACM.

GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference

Performance of metropolis algorithm for the minimum weight code word problem

In this article, we formulate and study quantum analogues of randomized search heuristics, which make use of Grover search (in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212-219. ACM, New York, 1996) to accelerate the search for improved offsprings. We then specialize the above formulation to two specific search heuristics: Random Local Search and the (1+1) Evolutionary Algorithm. We call the resulting quantum versions of these search heuristics Quantum Local Search and the (1+1) Quantum Evolutionary Algorithm. We conduct a rigorous runtime analysis of these quantum search heuristics in the computation model of quantum algorithms, which, besides classical computation steps, also permits those unique to quantum computing devices. To this end, we study the six elementary pseudo-Boolean optimization problems OneMax, LeadingOnes, Discrepancy, Needle, Jump, and TinyTrap. It turns out that the advantage of the respective quantum search heuristic over its classical counterpart varies with the problem structure and ranges from no speedup at all for the problem Discrepancy to exponential speedup for the problem TinyTrap. We show that these runtime behaviors are closely linked to the probabilities of performing successful mutations in the classical algorithms. © 2013 Springer Science+Business Media New York.

Fulltext

Algorithmica

Evolutionary algorithms for quantum computers

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.

SIAM Journal on Computing

Fast integer multiplication using modular arithmetic

We give the first polynomial-time algorithm for checking whether the Galois group Gal ( f ) of an input polynomial f (X) ε f[X] is nilpotent: the running time of our algorithm is bounded by a polynomial in the size of the coefficients of f and the degree of f. Additionally, we give a deterministic polynomial-time algorithm that, when given as input a polynomial f (X) ε f[X] with nilpotent Galois group, computes for each prime factor p of #Gal (f), a polynomial gp(X) ε f[X] whose Galois group of is the p-Sylow subgroup of Gal (f). © 2012 ACM.

ACM Transactions on Algorithms

Testing nilpotence of galois groups in polynomial time

In this paper, we study cyclic stabiliser codes over Fp of length dividing pt + 1 for some positive integer t. We call these t-Frobenius codes or just Frobenius codes for short. We give methods to construct them and show that they have efficient decoding algorithms. An important subclass of stabiliser codes are the linear stabiliser codes. For linear Frobenius codes we have stronger results: We completely characterise all linear Frobenius codes. As a consequence, we show that for every integer n that divides pt + 1 for an odd t, there are no linear cyclic codes of length n. On the other hand for even t, we give an explicit method to construct all of them. This gives us many explicit examples of Frobenius code which include the well studied Laflamme code. We show that the classical notion of BCH distance can be generalised to all the Frobenius codes that we construct, including the non-linear ones, and show that the algorithm of Berlekamp can be generalised to correct quantum errors within the BCH limit. This gives, for the first time, a family of codes that are neither CSS nor linear for which efficient decoding algorithm exits. © 2011 IEEE.

Quantum cyclic code of length dividing pt + 1

In this paper we study the suitability of the Metropolis Algorithm and its generalization for solving the shortest lattice vector problem (SVP). SVP has numerous applications spanning from robotics to computational number theory, viz., polynomial factorization. At the same time, SVP is a notoriously hard problem. Not only it is NP-hard, there is not even any polynomial approximation known for the problem that runs in polynomial time. What one normally uses is the LLL algorithm which, although a polynomial time algorithm, may give solutions which are an exponential factor away from the optimum. In this paper, we have defined an appropriate search space for the problem which we use for implementation of the Metropolis algorithm. We have defined a suitable neighbourhood structure which makes the diameter of the space polynomially bounded, and we ensure that each search point has only polynomially many neighbours. We can use this search space formulation for some other classes of evolutionary algorithms, e.g., for genetic and go-with-the-winner algorithms. We have implemented the Metropolis algorithm and Hasting's generalization of Metropolis algorithm for the SVP. Our results are quite encouraging in all instances when compared with LLL algorithm. © 2011 IEEE.

Proceedings of the 2011 11th International Conference on Hybrid Intelligent Systems, HIS 2011

Metropolis algorithm for solving Shortest lattice Vector Problem (SVP)

In this article, we formulate for the first time the notion of a quantum evolutionary algorithm. In fact we define a quantum analogue for any elitist (1+1) randomized search heuristic. The quantum evolutionary algorithm, which we call (1+1) quantum evolutionary algorithm (QEA), is the quantum version of the classical (1+1) evolutionary algorithm (EA), and runs only on a quantum computer. It uses Grover search [13] to accelerate the search for improved offsprings. To understand the speedup of the (1+1) QEA over the (1+1) EA, we study the three well known pseudo-Boolean optimization problems ONEMAX, LEADINGONES, and DISCREPANCY. We show that although there is a speedup in the case of ONEMAX and LEADINGONES in the quantum setting, the speedup is less than quadratic. For DISCREPANCY, we show that the speedup is at best constant. The reason for this inconsistency is due to the difference in the probability of making a successful mutation. On the one hand, if the probability of making a successful mutation is large then quantum acceleration does not help much. On the other hand, if the probabilities of making a successful mutation is small then quantum enhancement indeed helps. Copyright 2010 ACM.

Proceedings of the 12th Annual Genetic and Evolutionary Computation Conference, GECCO '10

Can quantum search accelerate evolutionary algorithms?

In this paper we formulate and study the problem of representing groups on graphs. We show that with respect to polynomial time Turing reducibility, both abelian and solvable group representability are all equivalent to graph isomorphism, even when the group is presented as a permutation group via generators. On the other hand, the representability problem for general groups on trees is equivalent to checking, given a group G and n, whether a nontrivial homomorphism from G to S n exists. There does not seem to be a polynomial time algorithm for this problem, in spite of the fact that tree isomorphism has polynomial time algorithms. © 2009 Springer Berlin Heidelberg.

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

Representing groups on graphs

Runtime analysis of evolutionary algorithms has become an important part in the theoretical analysis of randomized search heuristics. The first combinatorial problem where rigorous runtime results have been achieved is the well-known single source shortest path (SSSP) problem. Scharnow, Tin-nefeld and Wegener [PPSN 2002, J. Math. Model. Alg. 2004] proposed a multi-objective approach which solves the problem in expected polynomial time. They also suggest a related single-objective fitness function. However, it was left open whether this does solve the problem efficiently, and, in a broader context, whether multi-objective fitness functions for problems like the SSSP yield more efficient evolutionary algorithms. In this paper, we show that the single objective approach yields an efficient (1+1) EA with runtime bounds very close to those of the multi-objective approach. Copyright 2009 ACM.

Proceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09

Computing single source shortest paths using single-objective fitness functions

We give an O(N · log N ̇ 2O (log* N )algorithm for multiplying two N-bit integers that improves the O(N · log N · log log N) algorithm by Schönhage-Strassen |10|. Both these algorithms use modular arithmetic. Recently, Fürer |2| gave an O(N · log N ̇ 2O (log* N ) algorithm which however uses arithmetic over complex numbers as opposed to modular arithmetic. In this paper, we use multivariate polynomial multiplication along with ideas fron Fürer's algorithm to achieve this improvement in the modular setting. Our algorithm can also be viewed as a p-adic version of Fürer's algorithm. Thus, we show that the two seemingly different approaches to integer multiplication, modular and complex arithmetic, are similar. Copyright 2008 ACM.

Proceedings of the Annual ACM Symposium on Theory of Computing

We show that Graph Isomorphism is in the complexity class SPP, and hence it is in ⊕P (in fact, in ModkP for each k ≥ 2). These inclusions for Graph Isomorphism were not known prior to membership in SPP. We derive this result as a corollary of a more general result: we show that a generic problem FIND-GROUP has an FPSPP algorithm. This general result has other consequences: for example, it follows that the hidden subgroup problem for permutation groups, studied in the context of quantum algorithms, has an FPSPP algorithm. Also, some other algorithmic problems over permutation groups known to be at least as hard as Graph Isomorphism (e.g., coset intersection) are in SPP, and thus in ModkP for each k ≥ 2. © 2006 Elsevier Inc. All rights reserved.

Information and Computation

Graph Isomorphism is in SPP

We give a deterministic polynomial-time algorithm to check whether the Galois group Gal (f) of an input polynomial f(X) ∈ ℚ[X] is nilpotent: the running time is polynomial in size (f). Also, we generalize the Landau-Miller solvability test to an algorithm that tests if Gal (f) is in Τd: this algorithm runs in time polynomial in size (f) and n d and, moreover, if Gal (f) ∈ Τd it computes all the prime factors of #Gal (f). © Springer-Verlag Berlin Heidelberg 2006.

A polynomial time nilpotence test for galois groups and related results

In this paper we study the complexity of Bounded Color Multiplicity Graph Isomorphism BCGIb: the input is a pair of vertex-colored graphs such that the number of vertices of a given color in an input graph is bounded by b. We show that BCGIb is in the #L hierarchy (more precisely, the ModkL hierarchy for some constant k depending on b). Combined with the fact that Bounded Color Multiplicity Graph Isomorphism is logspace many-one hard for every set in the Modk L hierarchy for any constant k, we get a tight classification of the problem using logspace-bounded counting classes. © 2005 IEEE.

Proceedings of the Annual IEEE Conference on Computational Complexity

Bounded color multiplicity graph isomorphism is in the #L hierarchy

Given an algebraic number field K, such that [K : ℚ] is constant, we show that the problem of computing the units group φ*K is in the complexity class SPP. As a consequence, we show that principal ideal testing for an ideal in φK is in SPP. Furthermore, assuming the GRH, the class number of K, and a presentation for the class group of K can also be computed in SPP. A corollary of our result is that solving PELL'S EQUATION, recently shown by Hallgren [12] to have a quantum polynomial-time algorithm, is also in SPP. © Springer-Verlag Berlin Heidelberg 2004.

On the complexity of computing units in a number field

This paper is motivated by the computer-generated nonadditive code described in Rains et al[1]. We describe a theory of non-stabilizer codes of which the nonadditive code of Rains et al is an example. Furthermore, we give a general strategy of constructing good nonstabilizer codes from good stabilizer codes and give some explicit constructions and asymptotically good nonstabilizer codes. Like in the case of stabilizer codes, we can design fairly efficient encoding and decoding procedures. © Rinton Press.

Quantum Information and Computation

Non-stabilizer quantum codes from abelian subggroups of the error group

Assuming the generalized Riemann hypothesis, we prove the following complexity bounds: The order of the Galois group of an arbitrary polynomial f(x) ∈ ℤ[x] can be computed in P#P. Furthermore, the order can be approximated by a randomized polynomial-time algorithm with access to an NP oracle. For polynomials f with solvable Galois group we show that the order can be computed exactly by a randomized polynomial-time algorithm with access to an NP oracle. For all polynomiab f with abelian Galois group we show that a generator set for the Galois group can be computed in randomized polynomial time. © Springer-Verlag Berlin Heidelberg 2003.