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

DOI10.1090/mcom/3284zbMath1393.68058arXiv1609.02103OpenAlexW2962754399MaRDI QIDQ4637587

Henry K. Schenck, Klim Efremenko, Jerzy Weyman, Joseph M. Landsberg

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 complexityfree resolutiondeterminantpermanent

Mathematics Subject Classification ID

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

Related Items (4)

Geometric complexity theory and matrix powering ⋮ Lower bounds by Birkhoff interpolation ⋮ From grids to pseudo-grids of lines: Resolution and seminormality ⋮ Flattenings and Koszul Young flattenings arising in complexity theory

Cites Work

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

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