Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-048 | 14th March 2017 10:40

A note on monotone real circuits

RSS-Feed




TR17-048
Authors: Pavel Hrubes, Pavel Pudlak
Publication: 14th March 2017 10:42
Downloads: 1841
Keywords: 


Abstract:

We show that if a Boolean function $f:\{0,1\}^n\to \{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(sn^{k-2})$ which uses unary or binary monotone gates only. This partially solves an open problem presented in [Filmus,Hrubes,Lauria 2016]. In fact, in size $O(sn^{k-1})$, the circuit uses only unary monotone gates and binary addition. We also show that if the monotone Karchmer-Wigerson 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.



ISSN 1433-8092 | Imprint