TR17-048 Authors: Pavel Hrubes, Pavel Pudlak

Publication: 14th March 2017 10:42

Downloads: 520

Keywords:

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.