On minimal free resolutions of sub-permanents and other ideals arising in complexity theory

JOURNAL OF ALGEBRA

卷:503

Article

Efremenko, Klim¹  Landsberg, J. M.²  Schenck, Hal³  Weyman, Jerzy⁴ 

[1] Ben Gurion Univ Negev, Dept Comp Sci, Beer Sheva, Israel

[2] Texas A&M Univ, Dept Math, College Stn, TX 77843 USA

[3] Iowa State Univ, Dept Math, Ames, IA 50011 USA

[4] Univ Connecticut, Dept Math, Storrs, CT USA

关键词: Computational complexity;    Free resolution;    Determinant;    Permanent;   

DOI  :  10.1016/j.jalgebra.2018.01.021

来源: Elsevier

【 摘 要 】

We compute the linear strand of the minimal free resolution of the ideal generated by k x k sub-permanents of an n x n generic matrix and of the ideal generated by square-free monomials of degree k. The latter calculation gives the full minimal free resolution by [1]. Our motivation is to lay groundwork for the use of commutative algebra in algebraic complexity theory. We also compute several Hilbert functions relevant for complexity theory. (C) 2018 Elsevier Inc. All rights reserved.

【 授权许可】

Free