KIAM Main page Web Library  •  Publication Searh   

Article collection "Mathematical Problems of Cybernetics" 20, Moscow, 2022
Authors: Seiwert H., Sergeev I.S., Jukna S.
Reciprocal inputs in arithmetic and tropical circuits
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.
arithmetic circuits, tropical circuits, reciprocal inputs, dynamic programming
Publication language: russian,  pages: 20 (p. 61-80)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Seiwert Hannes, University Frankfurt
  • Sergeev Igor Sergeevich, Institute 'Quantum'
  • Jukna Stasys, University