TR20-178 Authors: Stasys Jukna, Hannes Seiwert, Igor Sergeev

Publication: 30th November 2020 19:48

Downloads: 486

Keywords:

It is known that the size of monotone arithmetic $(+,\ast)$ circuits can be exponentially decreased by allowing just one division "at the very end," at the output gate. A natural question is: can the size of $(+,\ast)$ circuits be substantially reduced if we allow divisions "at the very beginning," that is, if besides nonnegative real constants and variables $x_1,\ldots,x_n$, the circuits can also use their reciprocals $1/x_1,\ldots,1/x_n$ as inputs. We answer this question in the negative: the gain in circuit size is then always at most quadratic.

Over tropical $(\min,+)$ and $(\max,+)$ semirings, division turns into subtraction; so, reciprocal inputs are then $-x_1,\ldots,-x_n$. We give the same negative answer also for tropical circuits. The question of whether reciprocal inputs can substantially speed up tropical $(\min,+,\max)$ circuits, using both $\min$ and $\max$ gates, remains open.