Number of the records: 1
A note on monotone real circuits
- 1.
SYSNO ASEP 0482972 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title A note on monotone real circuits Author(s) Hrubeš, Pavel (MU-W) RID, SAI, ORCID
Pudlák, Pavel (MU-W) RID, SAISource Title Information Processing Letters. - : Elsevier - ISSN 0020-0190
Roč. 131, March (2018), s. 15-19Number of pages 5 s. Language eng - English Country NL - Netherlands Keywords computational complexity ; monotone real circuit ; Karchmer-Wigderson game Subject RIV IN - Informatics, Computer Science OECD category Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) Institutional support MU-W - RVO:67985840 UT WOS 000423005700003 EID SCOPUS 85034417207 DOI 10.1016/j.ipl.2017.11.002 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2019
Number of the records: 1