Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR17-048 | 14th March 2017 10:40

#### A note on monotone real circuits

TR17-048
Authors: Pavel Hrubes, Pavel Pudlak
Publication: 14th March 2017 10:42
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.