The method of shifted partial derivatives cannot separate the permanent from the determinant

DOI10.1090/MCOM/3284MaRDI QIDQ4637587zbMATH OpenOpenAlexFDO

Authors Klim Efremenko, Hal Schenck, J. M. Landsberg, Jerzy Weyman

Publication date 24 April 2018

Published in Mathematics of Computation (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitydeterminantfree resolutionpermanent

Mathematics Subject Classification ID

Syzygies, resolutions, complexes and commutative rings (13D02) Solving polynomial systems; resultants (13P15) Group actions on varieties or schemes (quotients) (14L30) Symmetric groups (20B30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symbolic computation and algebraic computation (68W30)

Abstract: The method of shifted partial derivatives was used to prove a super-polynomial lower bound on the size of depth four circuits needed to compute the permanent. We show that this method alone cannot prove that the padded permanent $el{l}^{n-m}per{m}_m$ cannot be realized inside the $G{L}_{n^2}$-orbit closure of the determinant $de{t}_n$ when $n>2m^2+2m$. Our proof relies on several simple degenerations of the determinant polynomial, Macaulay's theorem that gives a lower bound on the growth of an ideal, and a lower bound estimate from Gupta et. al. regarding the shifted partial derivatives of the determinant.

Recommendations

• Explicit polynomial sequences with maximal spaces of partial derivatives and a question of K. Mulmuley
• The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
• The shifted partial derivative complexity of elementary symmetric polynomials
• Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant's conjecture
• Geometry of orbits of permanents and determinants

Cites work

• Arithmetic circuits: a chasm at depth 3
• Arithmetic circuits: the chasm at depth four gets wider
• Eine Bedingung für die Flachheit und das Hilbertpolynom eines graduierten Ringes
• Equations for secant varieties of Veronese and other varieties
• scientific article; zbMATH DE number 1305008 (Why is no real title available?)
• Improved bounds for reduction to depth 4 and depth 3
• Lower bounds on arithmetic circuits via partial derivatives
• On minimal free resolutions of sub-permanents and other ideals arising in complexity theory
• The Parallel Evaluation of General Arithmetic Expressions
• Unifying known lower bounds via geometric complexity theory

Cited in

(6)

• Geometric complexity theory and matrix powering
• Geometry of orbits of permanents and determinants
• Flattenings and Koszul Young flattenings arising in complexity theory
• Lower bounds by Birkhoff interpolation
• From grids to pseudo-grids of lines: resolution and seminormality
• Young flattenings in the Schur module basis

This page was built for publication: The method of shifted partial derivatives cannot separate the permanent from the determinant

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