ECCC-Report TR19-034https://eccc.weizmann.ac.il/report/2019/034Comments and Revisions published for TR19-034en-usWed, 12 Aug 2020 11:21:09 +0300
Revision 1
| On $\epsilon$-sensitive monotone computations |
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2019/034#revision1We show that strong-enough lower bounds on monotone arithmetic circuits or the non-negative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial $f\in {\mathbb {R}}[x_1,\dots, x_n]$ of degree $d$ has an arithmetic circuit of size $s$ then $(x_1+\dots+x_n+1)^d+\epsilon f$ has a monotone arithmetic circuit of size $O(sd^2+n\log n)$, for some $\epsilon>0$. Second, if $f:\{0,1\}^n\rightarrow \{0,1\}$ is a Boolean function, we associate with $f$ an explicit exponential-size matrix $M(f)$ such that the Boolean circuit size of $f$ is at least $\Omega(\min_{\epsilon >0}(\hbox{rk}_+(M(f)-\epsilon J))- 2n)$, where $J$ is the all-ones matrix and $\hbox{rk}_+$ denotes the non-negative rank of a matrix. In fact, the quantity $\min_{\epsilon >0}(\hbox{rk}_+(M(f)-\epsilon J))$ characterizes how hard is it to distinguish rejecting and accepting inputs of $f$ by means of a linear program.
Finally, we introduce a proof system resembling the Boolean monotone calculus and show that similar $\epsilon$-sensitive lower bounds on monotone arithmetic circuits imply lower bounds on proof-size in the system. Wed, 12 Aug 2020 11:21:09 +0300https://eccc.weizmann.ac.il/report/2019/034#revision1
Paper TR19-034
| On $\epsilon$-sensitive monotone computations |
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2019/034We show that strong-enough lower bounds on monotone arithmetic circuits or the non-negative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial $f\in {\mathbb {R}}[x_1,\dots, x_n]$ of degree $d$ has an arithmetic circuit of size $s$ then $(x_1+\dots+x_n+1)^d+\epsilon f$ has a monotone arithmetic circuit of size $O(sd^2+n\log n)$, for some $\epsilon>0$. Second, if $f:\{0,1\}^n\rightarrow \{0,1\}$ is a Boolean function, we associate with $f$ an explicit exponential-size matrix $M(f)$ such that the Boolean circuit size of $f$ is at least $\Omega(\min_{\epsilon >0}(\hbox{rk}_+(M(f)-\epsilon J))- 2n)$, where $J$ is the all-ones matrix and $\hbox{rk}_+$ denotes the non-negative rank of a matrix. In fact, the quantity $\min_{\epsilon >0}(\hbox{rk}_+(M(f)-\epsilon J))$ characterizes how hard is it to distinguish rejecting and accepting inputs of $f$ by means of a linear program.
Finally, we introduce a proof system resembling the Boolean monotone calculus and show that similar $\epsilon$-sensitive lower bounds on monotone arithmetic circuits imply lower bounds on proof-size in the system. Tue, 05 Mar 2019 15:06:08 +0200https://eccc.weizmann.ac.il/report/2019/034