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 of large sparsity are hard for the monotone analogues of all the known definitions of VPSPACE, except for the one due to Poizat.

We study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat '08, Koiran-Perifel '09, Malod '11, Mahajan-Rao '13) that is believed to be larger than VNP. We show an exponential separation between the monotone version of Poizat's definition, and monotone VNP. We also show that unlike their non-monotone counterparts, these monotone analogues are not equivalent, with exponential separations in some cases.

The primary motivation behind our work is to understand the monotone complexity of transparent polynomials, a concept that was recently introduced by Hrubeš and Yehudayoff (2021). In that context, we are able to show that transparent polynomials of large sparsity are hard for the monotone analogues of all definitions of VPSPACE, except for the one due to Poizat.

Corrected typo.

We study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat '08, Koiran-Perifel '09, Malod '11, Mahajan-Rao '13) that is believed to be larger than VNP. We show an exponential separation between the monotone version of Poizat's definition, and monotone VNP. We also show that unlike their non-monotone counterparts, these monotone analogues are not equivalent, with exponential separations in some cases.

The primary motivation behind our work is to understand the monotone complexity of transparent polynomials, a concept that was recently introduced by Hrubeš and Yehudayoff (2021). In that context, we are able to show that transparent polynomials of large sparsity are hard for the monotone analogues of all definitions of VPSPACE, except for the one due to Poizat.

The draft has been simplified and shortened to now focus solely on the monotone classes beyond VNP.

Recently Hrubes and Yehudayoff (2021) showed a connection between the monotone algebraic circuit complexity of \emph{transparent} polynomials and a geometric complexity measure of their Newton polytope. They then used this connection to prove lower bounds against monotone VP (mVP). We extend their work by showing that their technique can be used to prove lower bounds against classes that are seemingly more powerful than monotone VNP (mVNP).

In the process, we define a natural monotone analogue of VPSPACE --- a well-studied class in the non-monotone setting (Poizat (2008), Koiran Perifel (2009), Malod (2011), Mahajan Rao (2013) --- and prove an exponential separation between the computational powers of this class and mVNP.

To show this separation, we define a new polynomial family with an interesting combinatorial structure which we use heavily in our lower bound. Both the polynomial and the combinatorial nature of our proof might be of independent interest.

We study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat '08, Koiran-Perifel '09, Malod '11, Mahajan-Rao '13) that is believed to be larger than VNP. We show an exponential separation between the monotone version of Poizat's definition, and monotone VNP. We also show that unlike their non-monotone counterparts, these monotone analogues are not equivalent, with exponential separations in some cases.

The primary motivation behind our work is to understand the monotone complexity of transparent polynomials, a concept that was recently introduced by Hrubeš and Yehudayoff (2021). In that context, we are able to show that transparent polynomials of large sparsity are hard for the monotone analogues of all definitions of VPSPACE, except for the one due to Poizat.

The draft has been simplified and shortened to now focus solely on the monotone classes beyond VNP.

Recently Hrubes and Yehudayoff (2021) showed a connection between the monotone algebraic circuit complexity of \emph{transparent} polynomials and a geometric complexity measure of their Newton polytope. They then used this connection to prove lower bounds against monotone VP (mVP). We extend their work by showing that their technique can be used to prove lower bounds against classes that are seemingly more powerful than monotone VNP (mVNP).

In the process, we define a natural monotone analogue of VPSPACE --- a well-studied class in the non-monotone setting (Poizat (2008), Koiran Perifel (2009), Malod (2011), Mahajan Rao (2013) --- and prove an exponential separation between the computational powers of this class and mVNP.

To show this separation, we define a new polynomial family with an interesting combinatorial structure which we use heavily in our lower bound. Both the polynomial and the combinatorial nature of our proof might be of independent interest.