Lower bounds for the determinantal complexity of explicit low degree polynomials

DOI10.1007/s00224-010-9308-1zbMath1222.68084OpenAlexW2170246176MaRDI QIDQ639850

Maurice Jansen

Publication date: 11 October 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-010-9308-1

zbMATH Keywords

computational complexityelementary symmetric polynomialarithmetic circuitsdeterminant versus permanent

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Depth-4 lower bounds, determinantal complexity: a unified approach

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• On computing the determinant in small parallel time using a small number of processors
• 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