On the complexity of the permanent in various computational models

DOI10.1016/J.JPAA.2017.02.008MaRDI QIDQ2013543zbMATHOpenAlexFDO

Authors Christian Ikenmeyer, J. M. Landsberg

Publication date 8 August 2017

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Abstract: We answer a question in [Landsberg, Ressayre, 2015], showing the regular determinantal complexity of the determinant det_m is O(m^3). We answer questions in, and generalize results of [Aravind, Joglekar, 2015], showing there is no rank one determinantal expression for perm_m or det_m when m >= 3. Finally we state and prove several "folklore" results relating different models of computation.

Recommendations

• scientific article; zbMATH DE number 5057518
• scientific article; zbMATH DE number 2151804
• Binary determinantal complexity
• 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 1332669 (Why is no real title available?)
• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• A lower bound for the determinantal complexity of a hypersurface
• Approaching the chasm at depth four
• Deterministic polynomial time algorithms for matrix completion problems
• Equations for secant varieties of Veronese and other varieties
• Fano schemes of determinants and permanents
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• Geometric aspects of iterated matrix multiplication
• Geometric complexity theory and matrix powering
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• Hypersurfaces with degenerate duals and the geometric complexity theory program
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• No occurrence obstructions in geometric complexity theory
• On the Expressive Power of Read-Once Determinants
• Padded polynomials, their cousins, and geometric complexity theory
• Permanent and determinant
• Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture
• Rectangular Kronecker coefficients and plethysms in geometric complexity theory
• Sur une généralisation du groupe orthogonal à quatre variables

Cited in

(12)

• Succinct Permanent Is NEXP-Hard with Many Hard Instances
• The Hafnian master theorem
• scientific article; zbMATH DE number 5839812 (Why is no real title available?)
• Binary determinantal complexity
• Computational complexity in non-Turing models of computation: the what, the why and the how
• Determinant versus permanent: salvation via generalization?
• Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture
• Expressing polynomials as the permanent of low rank square matrices
• Geometric complexity theory and matrix powering
• Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)
• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• A lower bound on determinantal complexity

This page was built for publication: On the complexity of the permanent in various computational models

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