Vikraman Arvind

STOC Conference 2024 Conference Paper

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time

• Vikraman Arvind
• Abhranil Chatterjee 0001
• Partha Mukhopadhyay

FOCS Conference 2024 Conference Paper

Trading Determinism for Noncommutativity in Edmonds' Problem

• Vikraman Arvind
• Abhranil Chatterjee 0001
• Partha Mukhopadhyay

Let $X=X_{1} \sqcup X_{2} \sqcup \ldots \sqcup X_{k}$ be a partitioned set of variables such that the variables in each part $X_{i}$ are noncommuting but for any $i\neq j$, the variables $x\in X_{i}$ commute with the variables $x^{\prime}\in X_{j}$. Given as input a square matrix $T$ whose entries are linear forms over $\mathbb{Q}\langle X\rangle$ 〉, we consider the problem of checking if $T$ is invertible or not over the universal skew field of fractions of the partially commutative polynomial ring $\mathbb{Q}\langle X\rangle$ [1]. In this paper, we design a deterministic polynomial-time algorithm for this problem for constant $k$. The special case $k=1$ is the noncommutative Edmonds' problem (NSINGULAR) which has a deterministic polynomial-time algorithm by recent results [2]–[4]. En-route, we obtain the first deterministic polynomial-time algorithm for the equivalence testing problem of $k$ -tape weighted automata (for constant $k$ ) resolving a longstanding open problem [5], [6]. Algebraically, the equivalence problem reduces to testing whether a partially commutative rational series over the partitioned set $X$ is zero or not [6]. Decidability of this problem was established by Harju and Karhumäki [5]. Prior to this work, a randomized polynomial-time algorithm for this problem was given by Worrell [6] and, subsequently, a deterministic quasipolynomial-time algorithm was also developed [7].

MFCS Conference 2023 Conference Paper

Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization

• Vikraman Arvind
• Pushkar S. Joglekar

Based on a theorem of Bergman [Cohn, 2006] we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, we show the following: 1) In the white-box setting, given an n-variate noncommutative polynomial f ∈ 𝔽⟨X⟩ over a field 𝔽 (either a finite field or the rationals) as an arithmetic circuit (or algebraic branching program), computing a complete factorization of f into irreducible factors is deterministic polynomial-time reducible to white-box factorization of a noncommutative bivariate polynomial g ∈ 𝔽⟨x, y⟩; the reduction transforms f into a circuit for g (resp. ABP for g), and given a complete factorization of g (namely, arithmetic circuits (resp. ABPs) for irreducible factors of g) the reduction recovers a complete factorization of f in polynomial time. We also obtain a similar deterministic polynomial-time reduction in the black-box setting. 2) Additionally, we show over the field of rationals that bivariate linear matrix factorization of 4× 4 matrices is at least as hard as factoring square-free integers. This indicates that reducing noncommutative polynomial factorization to linear matrix factorization (as done in [Vikraman Arvind and Pushkar S. Joglekar, 2022]) is unlikely to succeed over the field of rationals even in the bivariate case. In contrast, multivariate linear matrix factorization for 3×3 matrices over rationals is in polynomial time.

MFCS Conference 2021 Conference Paper

Equivalence Testing of Weighted Automata over Partially Commutative Monoids

• Vikraman Arvind
• Abhranil Chatterjee 0001
• Rajit Datta
• Partha Mukhopadhyay

Motivated by equivalence testing of k-tape automata, we study the equivalence testing of weighted automata in the more general setting, over partially commutative monoids (in short, pc monoids), and show efficient algorithms in some special cases, exploiting the structure of the underlying non-commutation graph of the monoid. Specifically, if the edge clique cover number of the non-commutation graph of the pc monoid is a constant, we obtain a deterministic quasi-polynomial time algorithm for equivalence testing. As a corollary, we obtain the first deterministic quasi-polynomial time algorithms for equivalence testing of k-tape weighted automata and for equivalence testing of deterministic k-tape automata for constant k. Prior to this, the best complexity upper bound for these k-tape automata problems were randomized polynomial-time, shown by Worrell [James Worrell, 2013]. Finding a polynomial-time deterministic algorithm for equivalence testing of deterministic k-tape automata for constant k has been open for several years [Emily P. Friedman and Sheila A. Greibach, 1982] and our results make progress. We also consider pc monoids for which the non-commutation graphs have an edge cover consisting of at most k cliques and star graphs for any constant k. We obtain a randomized polynomial-time algorithm for equivalence testing of weighted automata over such monoids. Our results are obtained by designing efficient zero-testing algorithms for weighted automata over such pc monoids.

MFCS Conference 2020 Conference Paper

A Special Case of Rational Identity Testing and the Brešar-Klep Theorem

• Vikraman Arvind
• Abhranil Chatterjee 0001
• Rajit Datta
• Partha Mukhopadhyay

We explore a special case of rational identity testing and algorithmic versions of two theorems on noncommutative polynomials, namely, Amitsur's theorem [S. A Amitsur, 1966] and the Brešar-Klep theorem [Brešar and Klep, 2008] when the input polynomial is given by an algebraic branching program (ABP). Let f be a degree-d n-variate noncommutative polynomial in the free ring Q<x_1, x_2, .. ., x_n> over rationals. 1) We consider the following special case of rational identity testing: Given a noncommutative ABP as white-box, whose edge labels are linear forms or inverses of linear forms, we show a deterministic polynomial-time algorithm to decide if the rational function computed by it is equivalent to zero in the free skew field Q<(X)>. Given black-box access to the ABP, we give a deterministic quasi-polynomial time algorithm for this problem. 2) Amitsur's theorem implies that if a noncommutative polynomial f is nonzero on k x k matrices then, in fact, f(M_1, M_2, .. ., M_n) is invertible for some matrix tuple (M_1, M_2, .. ., M_n) in (M_k(ℚ))^n. While a randomized polynomial time algorithm to find such (M_1, M_2, .. ., M_n) given black-box access to f is simple, we obtain a deterministic s^{O(log d)} time algorithm for the problem with black-box access to f, where s is the minimum ABP size for f and d is the degree of f. 3) The Brešar-Klep Theorem states that the span of the range of any noncommutative polynomial f on k x k matrices over Q is one of the following: zero, scalar multiples of I_k, trace-zero matrices in M_k(Q), or all of M_k(Q). We obtain a deterministic polynomial-time algorithm to decide which case occurs, given white-box access to an ABP for f. We also give a deterministic s^{O(log d)} time algorithm given black-box access to an ABP of size s for f. Our algorithms work when k >= d. Our techniques are based on some automata theory combined with known techniques for noncommutative ABP identity testing [Ran Raz and Amir Shpilka, 2005; Michael A. Forbes and Amir Shpilka, 2013].

MFCS Conference 2017 Conference Paper

Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings

• Vikraman Arvind
• Rajit Datta
• Partha Mukhopadhyay
• S. Raja 0001

In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring F{X}. Prior to this work, nonassociative arithmetic computation was considered by Hrubes, Wigderson, and Yehudayoff, and they showed lower bounds and proved completeness results. We consider Polynomial Identity Testing and Polynomial Factorization in F{X} and show the following results. 1. Given an arithmetic circuit C computing a polynomial f in F{X} of degree d, we give a deterministic polynomial algorithm to decide if f is identically zero. Our result is obtained by a suitable adaptation of the PIT algorithm of Raz and Shpilka for noncommutative ABPs. 2. Given an arithmetic circuit C computing a polynomial f in F{X} of degree d, we give an efficient deterministic algorithm to compute circuits for the irreducible factors of f in polynomial time when F is the field of rationals. Over finite fields of characteristic p, our algorithm runs in time polynomial in input size and p.

STOC Conference 2017 Conference Paper

Randomized polynomial time identity testing for noncommutative circuits

• Vikraman Arvind
• Pushkar S. Joglekar
• Partha Mukhopadhyay
• S. Raja 0001

In this paper we show that black-box polynomial identity testing for noncommutative polynomials f ∈𝔽⟨ z 1 , z 2 ,…, z n ⟩ of degree D and sparsity t , can be done in randomized ( n ,log t ,log D ) time. As a consequence, given a circuit C of size s computing a polynomial f ∈𝔽⟨ z 1 , z 2 ,…, z n ⟩ with at most t non-zero monomials, then testing if f is identically zero can be done by a randomized algorithm with running time polynomial in s and n and log t . This makes significant progress on a question that has been open for over ten years. Our algorithm is based on automata-theoretic ideas that can efficiently isolate a monomial in the given polynomial. In particular, we carry out the monomial isolation using nondeterministic automata.

MFCS Conference 2016 Conference Paper

The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs

• Vikraman Arvind
• Frank Fuhlbrück
• Johannes Köbler
• Sebastian Kuhnert
• Gaurav Rattan

In this paper we study the complexity of the following problems: 1. Given a colored graph X=(V, E, c), compute a minimum cardinality set of vertices S (subset of V) such that no nontrivial automorphism of X fixes all vertices in S. A closely related problem is computing a minimum base S for a permutation group G <= S_n given by generators, i. e. , a minimum cardinality subset S of [n] such that no nontrivial permutation in G fixes all elements of S. Our focus is mainly on the parameterized complexity of these problems. We show that when k=|S| is treated as parameter, then both problems are MINI[1]-hard. For the dual problems, where k=n-|S| is the parameter, we give FPT~algorithms. 2. A notion closely related to fixing is called individualization. Individualization combined with the Weisfeiler-Leman procedure is a fundamental technique in algorithms for Graph Isomorphism. Motivated by the power of individualization, in the present paper we explore the complexity of individualization: what is the minimum number of vertices we need to individualize in a given graph such that color refinement "succeeds" on it. Here "succeeds" could have different interpretations, and we consider the following: It could mean the individualized graph becomes: (a) discrete, (b) amenable, (c)compact, or (d) refinable. In particular, we study the parameterized versions of these problems where the parameter is the number of vertices individualized. We show a dichotomy: For graphs with color classes of size at most 3 these problems can be solved in polynomial time, while starting from color class size 4 they become W[P]-hard.

MFCS Conference 2012 Conference Paper

Approximate Graph Isomorphism

• Vikraman Arvind
• Johannes Köbler
• Sebastian Kuhnert
• Yadu Vasudev

Abstract We study optimization versions of Graph Isomorphism. Given two graphs G 1, G 2, we are interested in finding a bijection π from V ( G 1 ) to V ( G 2 ) that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an n O (log n ) time approximation scheme that for any constant factor α < 1, computes an α -approximation. We prove this by combining the n O (log n ) time additive error approximation algorithm of Arora et al. [ Math. Program. , 92, 2002] with a simple averaging algorithm. We also consider the corresponding minimization problem (of mismatches) and prove that it is NP -hard to α -approximate for any constant factor α. Further, we show that it is also NP -hard to approximate the maximum number of edges mapped to edges beyond a factor of 0. 94. We also explore these optimization problems for bounded color class graphs which is a well studied tractable special case of Graph Isomorphism. Surprisingly, the bounded color class case turns out to be harder than the uncolored case in the approximate setting.

MFCS Conference 2012 Conference Paper

Near-Optimal Expanding Generator Sets for Solvable Permutation Groups

• Vikraman Arvind
• Partha Mukhopadhyay
• Prajakta Nimbhorkar
• Yadu Vasudev

Abstract Let G = 〈 S 〉 be a solvable subgroup of the symmetric group S n given as input by the generator set S. We give a deterministic polynomial-time algorithm that computes an expanding generator set of size Õ( n 2 ) for G. As a byproduct of our proof, we obtain a new explicit construction of ε -bias spaces of size Õ \((n{\rm poly}({\rm log} d))({{1}\over{\varepsilon}})^{O(1)}\) for the groups \(\mathbb{Z}_d^n\).

STOC Conference 2010 Conference Paper

On the hardness of the noncommutative determinant

• Vikraman Arvind
• Srikanth Srinivasan 0001

MFCS Conference 2009 Conference Paper

Arithmetic Circuits, Monomial Algebras and Finite Automata

• Vikraman Arvind
• Pushkar S. Joglekar

Abstract We study lower bounds for circuit and branching program size over monomial algebras both in the noncommutative and commutative setting. Our main tool is automata theory and the main results are: An extension of Nisan’s noncommutative algebraic branching program size lower bounds [N91] over the free noncommutative ring \({\mathbb F}\langle{x_1, x_2, \cdots, x_n}\rangle\) to similar lower bounds over the noncommutative monomial algebras \({\ensuremath{\mathbb{F}}}\langle{x_1, x_2, \cdots, x_n}\rangle/I\) for a monomial ideal I generated by subexponential number of monomials. An extension of the exponential size lower bounds for monotone commutative circuits [JS82] computing the Permanent in ℚ[ x 11, x 12, ⋯, x nn ] to an exponential lower bound for monotone commutative circuits computing the Permanent in any monomial algebra ℚ[ x 11, x 12, ⋯, x nn ]/ I such that the monomial ideal I is generated by o ( n /log n ) monomials.

MFCS Conference 2006 Conference Paper

A Polynomial Time Nilpotence Test for Galois Groups and Related Results

• Vikraman Arvind
• Piyush P. Kurur

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

FOCS Conference 2002 Conference Paper

Graph Isomorphism is in SPP

• Vikraman Arvind
• Piyush P. Kurur

We show that graph isomorphism is in the complexity class SPP and hence it is in /spl oplus/P (in fact, it is in Mod/sub k/P for each k/spl ges/2). We derive this result as a corollary of a more general result: we show that a generic problem FIND-GROUP has an FP SPP 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 FP/sup SPP/ 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 Mod/sub k/P for each k>2.

TCS Journal 1995 Journal Article

If NP has polynomial-size circuits, then MA = AM

• Vikraman Arvind
• Johannes Köbler
• Uwe Schöning
• Rainer Schuler

It is shown that the assumption of NP having polynomial-size circuits implies (apart from a collapse of the polynomial-time hierarchy as shown by Karp and Lipton) that the classes AM and MA of Babai's Arthur-Merlin hierarchy coincide. This means that also a certain inner collapse of the remaining classes of the polynomial-time hierarchy occurs.

MFCS Conference 1993 Conference Paper

Hausdorff Reductions to Sparse Sets and to Sets of High Information Content

• Vikraman Arvind
• Johannes Köbler
• Martin Mundhenk

Abstract We investigate the complexity of sets that have a rich internal structure and at the same time are reducible to sets of either low or very high information content. In particular, we show that every length-decreasing or word-decreasing self-reducible set that reduces to some sparse set via a non-monotone variant of the Hausdorff reducibility is low for Δ 2 p. Measuring the information content of a set by the space-bounded Kolmogorov complexity of its characteristic sequence, we further investigate the (non-uniform) complexity of sets A in EXPSPACE/poly that reduce to some set having very high information content. Specifically, we show that if the reducibility used has a certain property, called “reliability, ” then A in fact is reducible to a sparse set (under the same reducibility). As a consequence of our results, the existence of hard sets (under “reliable” reducibilities) of very high information content is unlikely for various complexity classes as for example NP, PP, and PSPACE.