TR22-071 Authors: Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay

Publication: 13th May 2022 18:36

Downloads: 591

Keywords:

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 circuits in an $\epsilon$-sensitive way as long as $\epsilon \ge 2^{-\Omega(n)}$.

(2) There exists a polynomial over $n$ variables that can be computed by polynomial size monotone circuits but cannot be computed by any monotone arithmetic branching program (ABP) of $n^{o(\log n)}$ size, even in an $\epsilon$-sensitive fashion as long as $\epsilon \ge n^{-\Omega(\log n)}$.

(3) There exists a polynomial over $n$ variables that can be computed by polynomial size monotone ABP but cannot be computed in $n^{o(\log n)}$ size by monotone formulas even in an $\epsilon$-sensitive way, when $\epsilon \ge n^{-\Omega(\log n)}$.

(4) There exists a polynomial over $n$ variables that can be computed by width-$4$ polynomial size monotone arithmetic branching programs (ABPs) but cannot be computed in $2^{o(n^{1/d})}$ size by monotone, unbounded fan-in formulas of product depth $d$ even in an $\epsilon$-sensitive way, when $\epsilon \ge 2^{-\Omega(n^{1/d})}$. This yields an $\epsilon$-sensitive separation of constant-depth monotone formulas and constant-width monotone ABPs. It seems that even an ordinary separation of the two classes was not known.

An interesting feature of our separations is that in each case the polynomial exhibited is obtained from a graph inner-product polynomial by choosing an appropriate graph topology. The closely related graph inner-product Boolean function for expander graphs was invented by Hayes [DM & TCS'11], also independently by Pitassi [2009], in the context of best-partition multiparty communication complexity.