Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > OVERLAPPING PARITIES:
Reports tagged with Overlapping Parities:
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