8 citations · 28 across the 39 of their papers we have counts for
35 papers · 1 filter
Rational Identity Testing for Noncommutative Circuits is in Polynomial Space
V. Arvind, Pushkar S. Joglekar
The rational identity testing problem, RIT, asks whether an input \emph{rational circuit}, computes the zero element of the free skew field. For rational \emph{formulas} the proble…
On the Expressibility of the Reconstructional Color Refinement
V. Arvind, Johannes Köbler, Oleg Verbitsky
One of the most basic facts related to the famous Ulam reconstruction conjecture is that the connectedness of a graph can be determined by the deck of its vertex-deleted subgraphs,…
A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
Vikraman Arvind, Pushkar S Joglekar
We study the noncommutative rank problem, ncRANK, of computing the rank of matrices with linear entries in noncommuting variables and the problem of noncommutative Rational Ide…
On a Hierarchy of Spectral Invariants for Graphs
V. Arvind, Frank Fuhlbrück, Johannes Köbler +1
We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by Fürer (Lin. Alg. Appl. 2010) based on the angles formed by the set of standard…
Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization
V. Arvind, Pushkar S. Joglekar
Based on a theorem of Bergman we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncomm…
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…