4 papers
A Quadratic Lower Bound for Noncommutative Circuits
Pratik Shastri
We prove that every fan-in noncommutative arithmetic circuit computing the palindrome polynomial has size . In particular, when we obtain an lower bound…
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…