KIAM Main page Web Library  •  Publication Searh   
Publication

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.
Keywords:
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,  orcid.org/0000-0002-2293-6542Goethe University Frankfurt
  • Sergeev Igor Sergeevich,  orcid.org/0000-0002-0622-0843Research Institute 'Quantum'
  • Jukna Stasys,  orcid.org/0000-0002-2786-9326Vilnius University