On the complexity of the permanent in various computational models

DOI10.1016/J.JPAA.2017.02.008zbMATH Open1379.68367arXiv1610.00159OpenAlexW2528287002MaRDI QIDQ2013543FDOQ2013543

Authors: Christian Ikenmeyer, J. M. Landsberg 

Publication date: 8 August 2017

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

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.

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

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

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)

Cites Work

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

Cited In (11)

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

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)