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

arithmetic circuitcomputational complexityconstant-freedeterminantpermanent

Mathematics Subject Classification ID

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

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

• Characterizing Valiant's algebraic complexity classes
• 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?)
• 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)

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

Describes a project that uses

Uses Software

• nauty
• OEIS
• Traces

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)