6 papers
Equivalence Testing of Weighted Automata over Partially Commutative Monoids
V. Arvind, Abhranil Chatterjee, Rajit Datta +1
We study \emph{multiplicity equivalence} testing of automata over partially commutative monoids (pc monoids) and show efficient algorithms in special cases, exploiting the structur…
On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials
V. Arvind, Abhranil Chatterjee, Rajit Datta +1
We study the arithmetic circuit complexity of some well-known family of polynomials through the lens of parameterized complexity. Our main focus is on the construction of explicit…
Efficient Black-Box Identity Testing over Free Group Algebra
V. Arvind, Abhranil Chatterjee, Rajit Datta +1
Hrubeš and Wigderson [HW14] initiated the study of noncommutative arithmetic circuits with division computing a noncommutative rational function in the free skew field, and raised…
Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators
V. Arvind, Abhranil Chatterjee, Rajit Datta +1
Let be the polynomial ring over the variables . An ideal generated by univariate polynomia…
Fast Exact Algorithms Using Hadamard Product of Polynomials
V. Arvind, Abhranil Chatterjee, Rajit Datta +1
Let be an arithmetic circuit of size given as input that computes a polynomial , where and is any field whe…
A Note on Polynomial Identity Testing for Depth-3 Circuits
V. Arvind, Abhranil Chatterjee, Rajit Datta +1
Let be a depth-3 arithmetic circuit of size at most , computing a polynomial (where = or ) and th…