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