ECCC-Report TR22-031https://eccc.weizmann.ac.il/report/2022/031Comments and Revisions published for TR22-031en-usSun, 23 Jul 2023 15:22:39 +0300
Revision 5
| Transparency Beyond VNP in the Monotone Setting |
Prerona Chatterjee,
Kshitij Gajjar,
Anamay Tengse
https://eccc.weizmann.ac.il/report/2022/031#revision5In 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.Sun, 23 Jul 2023 15:22:39 +0300https://eccc.weizmann.ac.il/report/2022/031#revision5
Revision 4
| Monotone Classes Beyond VNP |
Prerona Chatterjee,
Kshitij Gajjar,
Anamay Tengse
https://eccc.weizmann.ac.il/report/2022/031#revision4We 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.Mon, 26 Sep 2022 23:47:38 +0300https://eccc.weizmann.ac.il/report/2022/031#revision4
Revision 3
| Monotone Classes Beyond VNP |
Prerona Chatterjee,
Kshitij Gajjar,
Anamay Tengse
https://eccc.weizmann.ac.il/report/2022/031#revision3We 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.Mon, 26 Sep 2022 23:39:39 +0300https://eccc.weizmann.ac.il/report/2022/031#revision3
Revision 2
| Transparency Beyond VNP in the Monotone Setting |
Prerona Chatterjee,
Kshitij Gajjar,
Anamay Tengse
https://eccc.weizmann.ac.il/report/2022/031#revision2Recently 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. Mon, 26 Sep 2022 18:38:06 +0300https://eccc.weizmann.ac.il/report/2022/031#revision2
Revision 1
| Monotone Classes Beyond VNP |
Prerona Chatterjee,
Kshitij Gajjar,
Anamay Tengse
https://eccc.weizmann.ac.il/report/2022/031#revision1We 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.Mon, 26 Sep 2022 14:10:21 +0300https://eccc.weizmann.ac.il/report/2022/031#revision1
Paper TR22-031
| Transparency Beyond VNP in the Monotone Setting |
Prerona Chatterjee,
Kshitij Gajjar,
Anamay Tengse
https://eccc.weizmann.ac.il/report/2022/031Recently 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. Sun, 27 Feb 2022 12:40:26 +0200https://eccc.weizmann.ac.il/report/2022/031