On Identity Testing and Noncommutative Rank Computation over the Free Skew Field
summary
Gives deterministic reductions and concrete bounds: a size-s rational formula with inversion height h is identity-preserving under a sparsification to 2(h+1) variables, and if nonzero must evaluate nontrivially on matrix tuples of dimension about (log s)/(h+1) using matrix-coefficient realization, so hardness for explicit noncommutative polynomials yields a quasipolynomial hitting set for constant h and a subexponential-time tester up to inversion height log s / log log s. Also extends white-box SINGULAR algorithms to matrices whose entries are small noncommutative formulas via a gadget linearization and proposes an inversely-disjoint r-skewed circuit model sitting between linear pencil and full rational classes.
AI-written summary · about