# Lower bounds for noncommutative arithmetic circuits with exact division?

It is known that for general arithmetic circuits there is not much of a difference between standard model and one with division: any circuit with divisions that computes a polynomial can be simulated by a circuit without divisions with only polynomial blow-up.

However, in the non-commutative world, such a reduction is unknown. In fact, although exponential lower bounds are known for noncommutative formulas without division, proving lower bounds for noncommutative formulas with division is a big open question.

Are we aware of lower bounds for noncommutative circuits with division, but where every gate computes a polynomial (and not just a rational function)?

• Since you are in a noncommutative setting, are there separate gate types for left and right division, or what? – Emil Jeřábek Jan 23 '16 at 14:12
• Good point! Sure, you should have left and right division. – ivmihajlin Jan 23 '16 at 17:24

To my knowledge, such a reduction is in fact known: Hrubes and Wigderson ITCS 2014 show how division gates can be eliminated from non-commutative circuits and formulas which compute polynomials.

They also provide exponential-size lower bounds for non-commutative formulas with division (not circuits) that compute any entry of the matrix inverse function $X^{-1}$.

Moreover, your main question about lower bounds for non-commutative circuits, is not known (while for formulas it is known as mentioned above), because non-commutative circuits in which each gate computes a polynomial (not a rational function) with division constitutes a class which is at least as strong as non-commutative circuits. But there is no known super-polynomial non-commutative circuit lower bound (see [Hrubes, Yehudayoff and Wigderson STOC 2010] on this).