\textsf{VNP} = \textsf{VP} in the multilinear world

DOI10.1016/J.IPL.2015.08.004zbMATH Open1346.68098OpenAlexW1128179352MaRDI QIDQ894473FDOQ894473

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

Recommendations

• On Hardness of Multilinearization and VNP-Completeness in Characteristic 2
• Strongly Exponential Separation between Monotone VP and Monotone VNP
• Characterizing Valiant’s Algebraic Complexity Classes
• On algebraic branching programs of small width
• Resource trade-offs in syntactically multilinear arithmetic circuits

zbMATH Keywords

computational complexityalgebraic complexitybranching programsmultilinear circuits

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Resource trade-offs in syntactically multilinear arithmetic circuits
• Characterizing Valiant's algebraic complexity classes
• Separating multilinear branching programs and formulas
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• The black-box query complexity of polynomial summation
• Algebraic Complexity Classes

This page was built for publication: \textsf{VNP} = \textsf{VP} in the multilinear world

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