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 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.

World University root node

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.

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

A polynomial time nilpotence test for galois groups and related results

A parser for simple Malayalam sentences

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.

Upper bounds on the complexity of some Galois theory problems (extended abstract)

We study projective dimension, a graph parameter, denoted by pd(G) for a bipartite graph G, introduced by Pudlák and Rödl (1992). For a Boolean function f (on n bits), Pudlák and Rödl associated a bipartite graph Gf and showed that size of the optimal branching program computing f, denoted by bpsize(f), is at least pd(Gf) (also denoted by pd(f)). Hence, proving lower bounds for pd(f) implies lower bounds for bpsize(f). Despite several attempts (Pudlák and Rödl (1992), Rónyai et al. (2000)), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive. We observe that there exist a Boolean function f for which the gap between the pd(f) and bpsize(f)) is 2Ω(n). Motivated by the argument in Pudlák and Rödl (1992), we define two variants of projective dimension: projective dimension with intersection dimension 1, denoted by upd(f), and bitwise decomposable projective dimension, denoted by bitpdim(f). We show the following results: (a) We observe that there exist a Boolean function f for which the gap between upd(f) and bpsize(f) is 2Ω(n). In contrast, we also show that the bitwise decomposable projective dimension characterizes size of the branching program up to a polynomial factor. That is, there exists a constant c &gt; 0 and for any function f, bitpdim(f)/6 ≤ bpsize(f) ≤ (bitpdim(f))c. (b) We introduce a new candidate family of functions f for showing super-polynomial lower bounds for bitpdim(f). As our main result, for this family of functions, we demonstrate gaps between pd(f) and the above two new measures for f: pd(f) = O(√n) &nbsp; upd(f) = Ω (n) &nbsp; bitpdim(f) = Ω (n1.5 / log n). We adapt Nechiporuk’s techniques for our linear algebraic setting to prove the best-known bpsize lower bounds for bitpdim. Motivated by this linear algebraic setting of our main result, we derive exponential lower bounds for two restricted variants of pd(f) and upd(f) by observing that they are exactly equal to well-studied graph parameters—bipartite clique cover number and bipartite partition number, respectively.