Non-commutative arithmetic circuits with division
Pavel Hrubeš, Avi Wigderson · 2014
We initiate the study of the complexity of arithmetic circuits with division gates over non-commuting variables. Such circuits and formulas compute non-commutative rational functions, which, despite their name, can no longer be expressed as ratios of polynomials. We prove some lower and upper bounds, completeness and simulation results, as follows.