Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #4 to TR22-031 | 26th September 2022 23:47

#### Monotone Classes Beyond VNP

Revision #4
Authors: Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse
Accepted on: 26th September 2022 23:47
Keywords:

Abstract:

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.

Changes to previous version:

Corrected typo.

Revision #3 to TR22-031 | 26th September 2022 23:39

#### Monotone Classes Beyond VNP

Revision #3
Authors: Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse
Accepted on: 26th September 2022 23:39
Keywords:

Abstract:

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.

Changes to previous version:

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

Revision #2 to TR22-031 | 26th September 2022 18:38

#### Transparency Beyond VNP in the Monotone Setting

Revision #2
Authors: Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse
Accepted on: 26th September 2022 18:38
Keywords:

Abstract:

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.

Revision #1 to TR22-031 | 26th September 2022 14:10

#### Monotone Classes Beyond VNP

Revision #1
Authors: Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse
Accepted on: 26th September 2022 14:10
Keywords:

Abstract:

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.

Changes to previous version:

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

### Paper:

TR22-031 | 16th February 2022 16:00

#### Transparency Beyond VNP in the Monotone Setting

TR22-031
Authors: Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse
Publication: 27th February 2022 12:40
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint