Monotone classes beyond VNP

DOI10.1016/J.TCS.2024.114689MaRDI QIDQ6589844zbMATH OpenFDO

Authors Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse

Publication date 20 August 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

algebraic circuit complexitymonotone computationVPSPACE

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 6820278 (Why is no real title available?)
• A \(\tau \)-conjecture for Newton polygons
• A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
• A lower bound on the number of additions in monotone computations
• A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
• Boolean function complexity. Advances and frontiers.
• Latin 2020: theoretical informatics. 14th Latin American symposium, São Paulo, Brazil, January 5--8, 2021. Proceedings
• Lower bounds for monotone arithmetic circuits via communication complexity
• Monotone projection lower bounds from extended formulation lower bounds
• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• Negation can be exponentially powerful
• On the depth complexity of formulas
• Separating monotone VP and VNP
• Small space analogues of Valiant's classes and the limitations of skew formulas
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Strongly Exponential Separation between Monotone VP and Monotone VNP
• Succinct algebraic branching programs characterizing non-uniform complexity classes
• The complexity of monotone computations of polynomials
• VPSPACE and a transfer theorem over the complex field

This page was built for publication: Monotone classes beyond VNP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6589844)