4 papers · 1 filter
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…
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…
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…