8 papers · 1 filter
On the Hardness of Order Finding and Equivalence Testing for ROABPs
C. Ramya, Pratik Shastri
The complexity of representing a polynomial by a Read-Once Oblivious Algebraic Branching Program (ROABP) is highly dependent on the chosen variable ordering. Bhargava et al. prove…
Efficient Polynomial Identity Testing Over Nonassociative Algebras
Partha Mukhopadhyay, C Ramya, Pratik Shastri
We design the first efficient polynomial identity testing algorithms over the nonassociative polynomial algebra. In particular, multiplication among the formal variables is commuta…
Lower bounds for planar Arithmetic Circuits
C. Ramya, Pratik Shastri
Arithmetic circuits are a natural well-studied model for computing multivariate polynomials over a field. In this paper, we study planar arithmetic circuits. These are circuits who…
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…
On Finer Separations between Subclasses of Read-once Oblivious ABPs
C. Ramya, Anamay Tengse
Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand…
Recent Progress on Matrix Rigidity -- A Survey
C. Ramya
The concept of matrix rigidity was introduced by Valiant(independently by Grigoriev) in the context of computing linear transformations. A matrix is rigid if it is far(in terms of…