We 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.

We 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.