Separating monotone VP and VNP

DOI10.1145/3313276.3316311zbMath1433.68154OpenAlexW2951593186MaRDI QIDQ5212783

Amir Yehudayoff

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3313276.3316311

zbMATH Keywords

algebraic complexitynon-negative rankmonotone computation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Monotone arithmetic complexity of graph homomorphism polynomials ⋮ On \(\epsilon\)-sensitive monotone computations ⋮ Unnamed Item ⋮ Regular expression length via arithmetic formula complexity ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Monotone circuit lower bounds from robust sunflowers ⋮ Limitations of sums of bounded read formulas and ABPs

This page was built for publication: Separating monotone VP and VNP