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

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

<p>Moreover, your main question about lower bounds for non-commutative <em>circuits</em>, 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).</p>

CC BY-SA 3.0
2016-01-24T01:16:30.563Z
2016-01-24T01:21:49.330Z
2016-01-24T01:21:49.330Z
Iddo Tzameret
<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2016-01-23T14:12:09.800Z
Since you are in a noncommutative setting, are there separate gate types for left and right division, or what?
Emil Jeřábek
CC BY-SA 3.0
2016-01-23T17:24:21.337Z
Good point! Sure, you should have left and right division.
ivmihajlin
<lower-bounds><arithmetic-circuits>
Lower bounds for noncommutative arithmetic circuits with exact division?
ivmihajlin
# Lower bounds for noncommutative arithmetic circuits with exact division?

(Asked by: username_0 on 2016-01-23)

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)?

**Tags:** lower-bounds, arithmetic-circuits

> **Comments:**
> **username_1**: Since you are in a noncommutative setting, are there separate gate types for left and right division, or what?  
> **username_0**: Good point! Sure, you should have left and right division.  

---

## 1 answers

### Answer by username_2 on 2016-01-24. Score: 8

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).


---

