Showing 2019Show all
2 papers · 1 filter
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…