\textsf{VNP} = \textsf{VP} in the multilinear world
From MaRDI portal
Publication:894473
DOI10.1016/j.ipl.2015.08.004zbMath1346.68098OpenAlexW1128179352MaRDI QIDQ894473
Nitin Saurabh, Meena Mahajan, Sébastien Tavenas
Publication date: 1 December 2015
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2015.08.004
Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Unnamed Item
- Unnamed Item
- Resource trade-offs in syntactically multilinear arithmetic circuits
- The black-box query complexity of polynomial summation
- Characterizing Valiant's algebraic complexity classes
- Algebraic Complexity Classes
- Arithmetic Circuits: A survey of recent results and open questions
- Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
- Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
- Separating multilinear branching programs and formulas