Reciprocal Inputs in Arithmetic and Tropical Circuits

S. Jukna, H. Seiwert, I. Sergeev

Abstract: 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.