ECCC-Report TR17-048https://eccc.weizmann.ac.il/report/2017/048Comments and Revisions published for TR17-048en-usTue, 14 Mar 2017 10:42:40 +0200
Paper TR17-048
| A note on monotone real circuits |
Pavel Pudlak,
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2017/048We 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.Tue, 14 Mar 2017 10:42:40 +0200https://eccc.weizmann.ac.il/report/2017/048