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.