1 citations · 1 across the 7 of their papers we have counts for
11 papers
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…
If VNP is hard, then so are equations for it
Mrinal Kumar, C. Ramya, Ramprasad Saptharishi +1
Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP does not have efficiently computable equations. In other words, a…