3 papers
cs.CC2025
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…
cs.CC2025
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…
cs.CC2025
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…