Monotone classes beyond VNP
From MaRDI portal
Publication:6589844
DOI10.1016/j.tcs.2024.114689MaRDI QIDQ6589844
Anamay Tengse, Kshitij Gajjar, Prerona Chatterjee
Publication date: 20 August 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- VPSPACE and a transfer theorem over the reals
- Boolean function complexity. Advances and frontiers.
- VPSPACE and a transfer theorem over the complex field
- The complexity of monotone computations of polynomials
- Negation can be exponentially powerful
- A lower bound on the number of additions in monotone computations
- Small space analogues of Valiant's classes and the limitations of skew formulas
- A \(\tau \)-conjecture for Newton polygons
- Latin 2020: theoretical informatics. 14th Latin American symposium, São Paulo, Brazil, January 5--8, 2021. Proceedings
- Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes
- On the depth complexity of formulas
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
- Separating monotone VP and VNP
- A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
- Strongly Exponential Separation between Monotone VP and Monotone VNP
- Lower bounds for monotone arithmetic circuits via communication complexity
This page was built for publication: Monotone classes beyond VNP
