8 citations · 28 across the 39 of their papers we have counts for
6 papers · 1 filter
On Identity Testing and Noncommutative Rank Computation over the Free Skew Field
V. Arvind, Abhranil Chatterjee, Utsab Ghosal +2
The identity testing of rational formulas (RIT) in the free skew field efficiently reduces to computing the rank of a matrix whose entries are linear polynomials in noncommuting va…
Recognizing the Commuting Graph of a Finite Group
V. Arvind, Peter. J. Cameron
In this paper we study the realizability question for commuting graphs of finite groups: Given an undirected graph is it the commuting graph of a group ? And if so, to deter…
Matrix Polynomial Factorization via Higman Linearization
V. Arvind, Pushkar S. Joglekar
In continuation to our recent work on noncommutative polynomial factorization, we consider the factorization problem for matrices of polynomials and show the following results. (1)…
Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time
V. Arvind, Abhranil Chatterjee, Partha Mukhopadhyay
Hrubeš and Wigderson (2015) initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem whic…
On Efficient Noncommutative Polynomial Factorization via Higman Linearization
V. Arvind, Pushkar S. Joglekar
In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x1,x2,...,xn over the field F.…
Isomorphism testing of -spanning tournaments is Fixed Parameter Tractable
Vikraman Arvind, Ilia Ponomarenko, Grigory Ryabov
An arc-colored tournament is said to be -spanning for an integer if the union of its arc-color classes of maximal valency at most is the arc set of a strongly conn…