Robustly Separating the Arithmetic Monotone Hierarchy via Graph Inner-Product

Abstract

We establish an ε-sensitive hierarchy separation for monotone arithmetic computations. The notion of ε-sensitive monotone lower bounds was recently introduced by Hrubeš [Pavel Hrubeš, 2020]. We show the following:  
- There exists a monotone polynomial over n variables in VNP that cannot be computed by 2^o(n) size monotone circuits in an ε-sensitive way as long as ε ≥ 2^(-Ω(n)). 
- 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 ε-sensitive fashion as long as ε ≥ n^(-Ω(log n)). 
- There exists a polynomial over n variables that can be computed by polynomial size monotone ABPs but cannot be computed in n^o(log n) size by monotone formulas even in an ε-sensitive way, when ε ≥ n^(-Ω(log n)). 
- 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 ε-sensitive way, when ε ≥ 2^(-Ω(n^{1/d})). This yields an ε-sensitive separation of constant-depth monotone formulas and constant-width monotone ABPs.  The novel 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 [Thomas P. Hayes, 2011], also independently by Pitassi [Toniann Pitassi, 2009], in the context of best-partition multiparty communication complexity.