Binary determinantal complexity

DOI10.1016/J.LAA.2016.04.027MaRDI QIDQ286175zbMATH OpenOpenAlexFDO

Authors 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)

Abstract: We prove that for writing the 3 by 3 permanent polynomial as a determinant of a matrix consisting only of zeros, ones, and variables as entries, a 7 by 7 matrix is required. Our proof is computer based and uses the enumeration of bipartite graphs. Furthermore, we analyze sequences of polynomials that are determinants of polynomially sized matrices consisting only of zeros, ones, and variables. We show that these are exactly the sequences in the complexity class of constant free polynomially sized (weakly) skew circuits.

Recommendations

• scientific article; zbMATH DE number 2151804
• On the complexity of the permanent in various computational models
• scientific article; zbMATH DE number 5057518
• A note on the determinant and permanent problem
• Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture

Cites work

• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• scientific article; zbMATH DE number 3187645 (Why is no real title available?)
• Characterizing Valiant's algebraic complexity classes
• Lower bounds on the bounded coefficient complexity of bilinear maps
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• On the Complexity of Matrix Product
• Practical graph isomorphism. II.
• The complexity of computing the permanent
• Valiant's model and the cost of computing integers

Cited in

(8)

• Rectangular Kronecker coefficients and plethysms in geometric complexity theory
• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• Permanent versus determinant: not via saturations
• A lower bound for the determinantal complexity of a hypersurface
• The boundary of the orbit of the 3-by-3 determinant polynomial
• On the complexity of the permanent in various computational models
• No occurrence obstructions in geometric complexity theory
• Determinantal complexities and field extensions

Describes a project that uses

Uses Software

• Traces
• OEIS
• nauty

This page was built for publication: Binary determinantal complexity

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