A note on monotone real circuits

0482972 - MÚ 2019 RIV NL eng J - Článek v odborném periodiku
Hrubeš, Pavel - Pudlák, Pavel
A note on monotone real circuits.
Information Processing Letters. Roč. 131, March (2018), s. 15-19. ISSN 0020-0190. E-ISSN 1872-6119
GRANT EU: European Commission(XE) 339691 - FEALORA
Institucionální podpora: RVO:67985840
Klíčová slova: computational complexity * monotone real circuit * Karchmer-Wigderson game
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impakt faktor: 0.914, rok: 2018
http://www.sciencedirect.com/science/article/pii/S0020019017301965?via%3Dihub

We show that if a Boolean function f:(0,1)n ... (0,1) can be computed by a monotone real circuit of size s using k-ary monotone gates then f can be computed by a monotone real circuit of size O(snk-2) which uses unary or binary monotone gates only. This partially solves an open problem presented in [2]. In fact, in size O(snk-1), the circuit uses only unary monotone gates and binary addition. We also show that if the monotone Karchmer-Wigderson game of f can be solved by a real communication protocol of size s then f can be computed by a monotone real circuit of the same size.
Trvalý link: http://hdl.handle.net/11104/0278383