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

DOI10.1090/MCOM/3284zbMATH Open1393.68058OpenAlexW2962754399MaRDI QIDQ4637587FDOQ4637587

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 complexitydeterminantpermanentfree resolution

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1305008 (Why is no real title available?)
• 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
• 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 (5)

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

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)