Monotone classes beyond VNP

In this work, we study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat 2008, Koiran & Perifel 2009, Malod 2011, Mahajan & Rao 2013) that is believed to be larger than VNP. We observe that these monotone analogues are not equivalent unlike their non-monotone counterparts, and propose monotone VPSPACE ( mVPSPACE ) to be defined as the monotone analogue of Poizat's definition. With this definition, mVPSPACE turns out to be exponentially stronger than mVNP and also satisfies several desirable closure properties that the other analogues may not. Our initial goal was to understand the monotone complexity of transparent polynomials, a concept that was recently introduced by Hrubeš & Yehudayoff (2021). In that context, we show that transparent polynomials with large support are hard for the monotone analogues of all the known definitions of VPSPACE, except for the one due to Poizat.

Authors

• Prerona Chatterjee
• Kshitij Gajjar
• Anamay Tengse

Keywords

• Algebraic circuit complexity
• Monotone computation
• VPSPACE