Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-031 | 16th February 2022 16:00

Transparency Beyond VNP in the Monotone Setting

RSS-Feed




TR22-031
Authors: Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse
Publication: 27th February 2022 12:40
Downloads: 186
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