Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MONOTONE VPSPACE:
Reports tagged with Monotone VPSPACE:
TR22-031 | 16th February 2022
Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse

Transparency Beyond VNP in the Monotone Setting

Revisions: 5

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 ... more >>>




ISSN 1433-8092 | Imprint