Article collection "Mathematical Problems of Cybernetics" №20, Moscow, 2022
Authors:Seiwert H., Sergeev I.S., Jukna S.
Reciprocal inputs in arithmetic and tropical circuits
Abstract:
It is known that the size of monotone arithmetic (+, ·) 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 (+, ·) circuits be substantially reduced if we allow divisions “at the very beginning,” that is, if besides nonnegative real constants and variables x1, …, xn, the circuits can also use their reciprocals 1/x1, ..., 1/xn 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 -x1, …, -xn. We give the same negative answer also for tropical circuits. The question of whether reciprocal inputs can substantially speed up tropical (min, +, max) circuits, remains open.
