Počet záznamů: 1
A note on monotone real circuits
- 1.
SYSNO ASEP 0482972 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název A note on monotone real circuits Tvůrce(i) Hrubeš, Pavel (MU-W) RID, SAI, ORCID
Pudlák, Pavel (MU-W) RID, SAIZdroj.dok. Information Processing Letters. - : Elsevier - ISSN 0020-0190
Roč. 131, March (2018), s. 15-19Poč.str. 5 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova computational complexity ; monotone real circuit ; Karchmer-Wigderson game Vědní obor RIV IN - Informatika Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) Institucionální podpora MU-W - RVO:67985840 UT WOS 000423005700003 EID SCOPUS 85034417207 DOI 10.1016/j.ipl.2017.11.002 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2019
Počet záznamů: 1