Binary determinantal complexity

DOI10.1016/j.laa.2016.04.027zbMath1357.68085arXiv1410.8202OpenAlexW1506761118MaRDI QIDQ286175

Jesko Hüttenhain, Christian Ikenmeyer

Publication date: 20 May 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.8202

zbMATH Keywords

computational complexitydeterminantpermanentarithmetic circuitconstant-free

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Enumeration in graph theory (05C30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A lower bound for the determinantal complexity of a hypersurface, Rectangular Kronecker coefficients and plethysms in geometric complexity theory, Permanent versus determinant: Not via saturations, No occurrence obstructions in geometric complexity theory

Uses Software

• nauty
• OEIS
• Traces

Cites Work

• The complexity of computing the permanent
• Valiant's model and the cost of computing integers
• Practical graph isomorphism. II.
• Characterizing Valiant's algebraic complexity classes
• Lower bounds on the bounded coefficient complexity of bilinear maps
• On the Complexity of Matrix Product
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item