Binary determinantal complexity

DOI10.1016/J.LAA.2016.04.027zbMATH Open1357.68085arXiv1410.8202OpenAlexW1506761118MaRDI QIDQ286175FDOQ286175

Jesko Hüttenhain, Christian Ikenmeyer

Publication date: 20 May 2016

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Practical graph isomorphism. II.
• The complexity of computing the permanent
• Title not available (Why is that?)
• Valiant's model and the cost of computing integers
• Characterizing Valiant's algebraic complexity classes
• Lower bounds on the bounded coefficient complexity of bilinear maps
• On the Complexity of Matrix Product
• Title not available (Why is that?)
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• Title not available (Why is that?)

Cited In (5)

• Rectangular Kronecker coefficients and plethysms in geometric complexity theory
• Title not available (Why is that?)
• A lower bound for the determinantal complexity of a hypersurface
• Permanent versus determinant: Not via saturations
• No occurrence obstructions in geometric complexity theory

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)