Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-178 | 30th November 2020 19:47

Reciprocal Inputs in Arithmetic and Tropical Circuits


Authors: Stasys Jukna, Hannes Seiwert, Igor Sergeev
Publication: 30th November 2020 19:48
Downloads: 486


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.

ISSN 1433-8092 | Imprint