Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-034 | 12th August 2020 11:21

On \epsilon-sensitive monotone computations

RSS-Feed




Revision #1
Authors: Pavel Hrubes
Accepted on: 12th August 2020 11:21
Downloads: 497
Keywords: 


Abstract:

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.


Paper:

TR19-034 | 5th March 2019 14:56

On \epsilon-sensitive monotone computations





TR19-034
Authors: Pavel Hrubes
Publication: 5th March 2019 15:06
Downloads: 1264
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint