Showing cs.CCShow all
2 papers · 1 filter
cs.CC2022
On Identity Testing and Noncommutative Rank Computation over the Free Skew Field
V. Arvind, Abhranil Chatterjee, Utsab Ghosal +2
The identity testing of rational formulas (RIT) in the free skew field efficiently reduces to computing the rank of a matrix whose entries are linear polynomials in noncommuting va…
cs.CC2021
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…