ECCC-Report TR22-071https://eccc.weizmann.ac.il/report/2022/071Comments and Revisions published for TR22-071en-usFri, 13 May 2022 18:36:48 +0300
Paper TR22-071
| Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product |
Utsab Ghosal,
Arkadev Chattopadhyay,
Partha Mukhopadhyay
https://eccc.weizmann.ac.il/report/2022/071 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.Fri, 13 May 2022 18:36:48 +0300https://eccc.weizmann.ac.il/report/2022/071