7
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.