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

DOI10.1090/MCOM/3284zbMATH Open1393.68058arXiv1609.02103OpenAlexW2962754399MaRDI 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)

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.

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

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

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)

Cites Work

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

Cited In (5)

• From grids to pseudo-grids of lines: Resolution and seminormality
• 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

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)