Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials

DOI10.1007/978-3-642-03351-3_17zbMath1248.68206OpenAlexW1492733017MaRDI QIDQ3392951

Maurice Jansen

Publication date: 18 August 2009

Published in: Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03351-3_17

zbMATH Keywords

computational complexityelementary symmetric polynomialdeterminantpermanentarithmetical circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

On the Expressive Power of Read-Once Determinants

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Feasible arithmetic computations: Valiant's hypothesis
• The complexity of partial derivatives
• Lower bounds on arithmetic circuits via partial derivatives
• Completeness and reduction in algebraic complexity theory
• Cook's versus Valiant's hypothesis
• PP is as Hard as the Polynomial-Time Hierarchy
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• Depth-3 arithmetic circuits over fields of characteristic zero

This page was built for publication: Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials