We establish an $\epsilon$-sensitive hierarchy separation for monotone arithmetic computations. The notion of $\epsilon$-sensitive monotone lower bounds was recently introduced by Hrubes [Computational Complexity'20]. We show the following:
(1) There exists a monotone polynomial over $n$ variables in VNP that cannot be computed by $2^{o(n)}$ size monotone ...
more >>>