Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > UTSAB GHOSAL:
All reports by Author Utsab Ghosal:

TR22-071 | 13th May 2022
Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay

Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product

We establish an $\epsilon$-sensitive hierarchy separation for monotone arithmetic computations. The notion of $\epsilon$-sensitive monotone lower bounds was recently introduced by Hrubes [Computational Complexity'20]. We show the following:

(1) There exists a monotone polynomial over $n$ variables in VNP that cannot be computed by $2^{o(n)}$ size monotone ... more >>>




ISSN 1433-8092 | Imprint