IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

The rigidity of a matrix A for target rank r is the minimum number of entries of A that must be changed to ensure that the rank of the altered matrix is at most r. Since its introduction by Valiant (1977), rigidity and similar rank-robustness functions of matrices have found numerous applications in circuit complexity, communication complexity, and learning complexity. Almost all n × n matrices over an infinite field have a rigidity of (n − r)2. It is a long-standing open question to construct infinite families of explicit matrices even with superlinear rigidity when r = Ω(n).In this paper, we construct an infinite family of complex matrices with the largest possible, i.e., (n − r)2, rigidity. The entries of an n × n matrix in this family are distinct primitive roots of unity of orders roughly exp(n2 log n). To the best of our knowledge, this is the first family of concrete (but not entirely explicit) matrices having maximal rigidity and a succinct algebraic description.Our construction is based on elimination theory of polynomial ideals. In particular, we use results on the existence of polynomials in elimination ideals with effective degree upper bounds (effective Nullstellensatz). Using elementary algebraic geometry, we prove that the dimension of the affine variety of matrices of rigidity at most k is exactly n2 – (n – r)2 + k. Finally, we use elimination theory to examine whether the rigidity function is semicontinuous. © 2013, Springer Basel.

Department of Computer Science and Engineering

Department of Management Studies

World University root node

Fulltext

Computational Complexity

Using Elimination Theory to Construct Rigid Matrices

We use algorithmic tools for graphs of small treewidth to address questions in complexity theory. For our main construction, we prove that multiplicatively disjoint arithmetic circuits of size n O(1) and treewidth k can be simulated by bounded fan-in arithmetic formulas of depth O(k 2logn). From this we derive an analogous statement for syntactically multilinear arithmetic circuits, which strengthens the central theorem of M. Mahajan and B.V.R. Rao (Proc. 33rd International Symposium on Mathematical Foundations of Computer Science, vol. 5162, pp. 455-466, 2008). We show our main construction has the following three applications: •Bounded width arithmetic circuits of size nO(1) can be balanced to depth O(logn), provided chains of iterated multiplication in the circuit are of length O(1). •Boolean bounded fan-in circuits of size nO(1) and treewidth k can be simulated by bounded fan-in formulas of depth O(k2logn). This strengthens in the non-uniform setting the known inclusion that SC0⊆NC1. •We demonstrate treewidth restricted cases of Directed-Reachability and Circuit Value Problem that can be solved in LogDCFL. We also give a construction showing, for both arithmetic and Boolean circuits, that any circuit of size nO(1) and treewidth O(login) can be simulated by a circuit of width O(logi+1n) and size nc, where c=O(1), if i=0, and c=O(loglogn) otherwise. © 2013 Springer Science+Business Media New York.

Theory of Computing Systems

Balancing Bounded Treewidth Circuits

We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results : - As our first main result, we prove that any homogeneous depth-3 circuit for computing the product of d matrices of dimension n x n requires Ω(nd-1/2d) size. This improves the lower bounds in [9] for d = ω(1). - As our second main result, we show that there is an explicit polynomial on n variables and degree at most n/2 for which any depth-3 circuit C of product dimension at most n/10 (dimension of the space of affine forms feeding into each product gate) requires size 2Ω(n). This generalizes the lower bounds against diagonal circuits proved in [14]. Diagonal circuits are of product dimension 1. - We prove a nΩ(log n) lower bound on the size of product-sparse formulas. By definition, any multilinear formula is a product-sparse formula. Thus, this result extends the known super-polynomial lower bounds on the size of multilinear formulas [11]. - We prove a 2 Ω(n) lower bound on the size of partitioned arithmetic branching programs. This result extends the known exponential lower bound on the size of ordered arithmetic branching programs [7]. © 2013 Springer-Verlag.

GENERAL

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

Arithmetic circuit lower bounds via MaxRank

We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced in [4]. Proving an exponential lower bound for the size of the non-deterministic thrifty branching programs would separate NL from P under the thrifty hypothesis. In this context, we consider a restriction of non-deterministic thrifty branching programs called bitwise-independence. We show that any bitwise-independent non-deterministic thrifty branching program solving BT2(h, k) must have at least 12 kh/2 states. Prior to this work, lower bounds were known for general branching programs only for fixed heights h = 2, 3, 4 [4]. Our lower bounds are also tight (up to a factor of k), since the known[4] non-deterministic thrifty branching programs for this problem of size O(kh/2+1) are bitwise-independent. We prove our results by associating a fractional pebbling strategy with any bitwise-independent nondeterministic thrifty branching program solving the Tree Evaluation Problem. Such a connection was not known previously even for fixed heights. Our main technique is the entropy method introduced by Jukna and Zak[6] originally in the context of proving lower bounds for read-once branching programs. We also show that the previous lower bounds known[4] for deterministic branching programs for Tree Evaluation Problem can be obtained using this approach. Using this method, we also show tight lower bounds for any k-way deterministic branching program solving Tree Evaluation Problem when the instances are restricted to have the same group operation in all internal nodes.

Leibniz International Proceedings in Informatics, LIPIcs

Pebbling, entropy and branching program size lower bounds

A normal Hall subgroup N of a group G is a normal subgroup with its order coprime with its index. Schur-Zassenhaus theorem states that every normal Hall subgroup has a complement subgroup, that is a set of coset representatives H which also forms a subgroup of G. In this paper, we present a framework to test isomorphism of groups with at least one normal Hall subgroup, when groups are given as multiplication tables. To establish the framework, we first observe that a proof of Schur-Zassenhaus theorem is constructive, and formulate a necessary and sufficient condition for testing isomorphism in terms of the associated actions of the semidirect products, and isomorphisms of the normal parts and complement parts. We then focus on the case when the normal subgroup is abelian. Utilizing basic facts of representation theory of finite groups and a technique by Le Gall (STACS 2009), we first get an efficient isomorphism testing algorithm when the complement has bounded number of generators. For the case when the complement subgroup is elementary abelian, which does not necessarily have bounded number of generators, we obtain a polynomial time isomorphism testing algorithm by reducing to generalized code isomorphism problem, which asks whether two linear subspaces are the same up to permutation of coordinates. A solution to the latter can be obtained by a mild extension of the singly exponential (in the number of coordinates) time algorithm for code isomorphism problem developed recently by Babai et al. (SODA 2011). Enroute to obtaining the above reduction, we study the following computational problem in representation theory of finite groups: given two representations ? and ? of a group H over Z d p , p a prime, determine if there exists an automorphism φ : H → H, such that the induced representation ?φ = ? 0 φ and ? are equivalent, in time poly(|H|, p d). © 2012 Springer Science+Business Media, LLC &amp; Science Press, China.

Journal of Computer Science and Technology

On isomorphism testing of groups with normal hall subgroups

We revisit a well studied linear algebraic problem, computing the rank and determinant of matrices, in order to obtain completeness results for small complexity classes. In particular, we prove that computing the rank of a class of diagonally dominant matrices is complete for L. We show that computing the permanent and determinant of tridiagonal matrices over ℤ is in GapNC1 and is hard for NC1. We also initiate the study of computing the rigidity of a matrix: the number of entries that needs to be changed in order to bring the rank of a matrix below a given value. We show that some restricted versions of the problem characterize small complexity classes. We also look at a variant of rigidity where there is a bound on the amount of change allowed. Using ideas from the linear interval equations literature, we show that this problem is NP-hard over ℚ and that a certain restricted version is NP-complete. Restricting the problem further, we obtain variations which can be computed in PL and are hard for C=L. © 2008 Springer Science+Business Media, LLC.

On the complexity of matrix rank and rigidity

The decrease of a Boolean function f : 0,1n →0,1, denoted by d(f) is the maximum number of inverse indices in any increasing chain of inputs, where i is an inverse index if f(xi) &gt; f(x i+1). It follows from a theorem of Markov (JACM 1958) that the minimum number of negation gates in a circuit necessary and sufficient to compute any Boolean function f is ⌈log(d(f) + 1)⌉. A recent result due to Morizumi (ICALP 2009) proves that d(f) negations are necessary and sufficient when the computation is done by formulas. We explore the situation in between formulas (directed trees) and general circuits (DAGs), and related models. We obtain the following results: 1. We argue that for any Boolean function f, there is a circuit computing f, that uses ⌈log(d(f) + 1)⌉ negations and has treewidth at most ⌈log(d(f) + 1)⌉ + 1. For 1 ≤ k ≤ ⌈log(d(f) + 1)⌉, we prove that d(f)·8k/2k negations are sufficient to compute any Boolean function f by circuits of treewidth at most k. Moreover, if there is a circuit family of size s = s(n) and treewidth k = k(n) computing fn, then there exists a circuit family of size s·nO(1)·2 O(min k,log n) and treewidth at most 2k which computes f n and contains O(max nk/22k,log n) negation gates. 2. We obtain tight bounds on the number of negation gates required to compute specific functions such as Parity2, Parity2 and Invertern by one-input-face upward planar circuits. We extend these lower bounds to a larger class of functions (which also includes natural functions like Add and Subtract) and we show a direct sum theorem for this class with respect to the number of negations. 3. We demonstrate the limitations of the one-input-face constraint in the upward planar circuits by showing the explicit function which can be computed by a monotone upward planar circuit, but cannot be computed by any montone one-input-face upward planar circuit. 4. We prove that for every Boolean function f, there exists a multilective upward planar circuit which uses at most ⌈d(f)+1/2⌉ negation gates for computing f. © 2010 Springer-Verlag.

Limiting negations in bounded treewidth and upward planar circuits

The P-complete Circuit Value Problem CVP, when restricted to monotone planar circuits MPCVP, is known to be in NC3, and for the special case of upward stratified circuits, it is known to be in LogDCFL. In this paper we re-examine the complexity of MPCVP, with special attention to circuits with cylindrical embeddings. We characterize cylindricality, which is stronger than planarity but strictly generalizes upward planarity, and make the characterization partially constructive. We use this construction, and four key reduction lemmas, to obtain several improvements. We show that stratified cylindrical monotone circuits can be evaluated in LogDCFL, and arbitrary cylindrical monotone circuits can be evaluated in AC1(LogDCFL), while monotone circuits with one-input-face planar embeddings can be evaluated in LogCFL. For monotone circuits with focused embeddings, we show an upper bound of AC1(LogDCFL). We re-examine the NC3 algorithm for general MPCVP, and note that it is in AC1(LogCFL) = SAC2. Finally, we consider extensions beyond MPCVP. We show that monotone circuits with toroidal embeddings can, given such an embedding, be evaluated in NC. Also, special kinds of arbitrary genus circuits can also be evaluated in NC. We also show that planar non-monotone circuits with polylogarithmic negation-height can be evaluated in NC.

Department of Mechanical Engineering

computational complexity

Upper Bounds for Monotone Planar Circuit Value and Variants

We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in Σp2<math xmlns="http://www.w3.org/1998/Math/MathML"><msubsup><mi mathvariant="normal">Σ</mi><mn>2</mn><mi>p</mi></msubsup></math>. In the case of linear matroids, which are represented over polynomially growing fields, we note that the problem is unlikely to be Σp2<math xmlns="http://www.w3.org/1998/Math/MathML"><msubsup><mi mathvariant="normal">Σ</mi><mn>2</mn><mi>p</mi></msubsup></math>-complete and is coNP-hard. We show that when the rank of the matroid is bounded by a constant, linear matroid isomorphism and matroid isomorphism are both polynomial time many-one equivalent to graph isomorphism.We give a polynomial time Turing reduction from graphic matroid isomorphism problem to the graph isomorphism problem. We then give a polynomial time many-one reduction from bounded rank matroid isomorphism problem to graphic matroid isomorphism, thus showing that all the above problems are polynomial time equivalent.Further, for linear and graphic matroids, we prove that the automorphism problem is polynomial time equivalent to the corresponding isomorphism problems. In addition, we give a polynomial time membership test algorithm for the automorphism group of a graphic matroid.

Department of Applied Mechanics

International Computer Science Symposium in Russia

On the Complexity of Matroid Isomorphism Problems

For the all-ones lower triangular matrices, the upper and lower bounds on rigidity are known to match [P. Pudlak, Z. Vavrin, Computation of rigidity of order n2 / r for one simple matrix, Comment Math. Univ. Carolin. 32 (2) (1991) 213-218]. In this short note, we apply these techniques to the all-ones extended lower triangular matrices, to obtain upper and lower bounds with a small gap between the two; we show that the rigidity is θ (frac(n2, r)). © 2008 Elsevier B.V. All rights reserved.