Monotone classes beyond VNP
From MaRDI portal
Publication:6589844
DOI10.1016/J.TCS.2024.114689MaRDI QIDQ6589844FDOQ6589844
Authors: Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse 
Publication date: 20 August 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
Cites Work
- Small space analogues of Valiant's classes and the limitations of skew formulas
- Boolean function complexity. Advances and frontiers.
- Negation can be exponentially powerful
- A lower bound on the number of additions in monotone computations
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- On the depth complexity of formulas
- A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
- Lower bounds for monotone arithmetic circuits via communication complexity
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- VPSPACE and a transfer theorem over the complex field
- A \(\tau \)-conjecture for Newton polygons
- Title not available (Why is that?)
- The complexity of monotone computations of polynomials
- Monotone projection lower bounds from extended formulation lower bounds
- Latin 2020: theoretical informatics. 14th Latin American symposium, São Paulo, Brazil, January 5--8, 2021. Proceedings
- Strongly Exponential Separation between Monotone VP and Monotone VNP
- Separating monotone VP and VNP
- Succinct algebraic branching programs characterizing non-uniform complexity classes
- A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
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)
