Number of the records: 1
A note on monotone real circuits
- 1.0482972 - MÚ 2019 RIV NL eng J - Journal Article
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
EU Projects: European Commission(XE) 339691 - FEALORA
Institutional support: RVO:67985840
Keywords : computational complexity * monotone real circuit * Karchmer-Wigderson game
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 0.914, year: 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.
Permanent Link: http://hdl.handle.net/11104/0278383
File Download Size Commentary Version Access Hrubes.pdf 4 264.6 KB Publisher’s postprint require
Number of the records: 1