8 papers
Monotone Complexity of Spanning Tree Polynomial Re-visited
Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal +1
We prove two results that shed new light on the monotone complexity of the spanning tree polynomial, a classic polynomial in algebraic complexity and beyond. First, we show that th…
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…