4 papers · 1 filter
Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time
V. Arvind, Abhranil Chatterjee, Partha Mukhopadhyay
Hrubeš and Wigderson (2015) initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem whic…
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…