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

abstract

• 2018 Elsevier Inc. We compute the linear strand of the minimal free resolution of the ideal generated by kk sub-permanents of an nn 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.

authors

• Landsberg, Joseph

published proceedings

• JOURNAL OF ALGEBRA

author list (cited authors)

• Efremenko, K., Landsberg, J. M., Schenck, H., & Weyman, J.

citation count

• 2

complete list of authors

• Efremenko, Klim||Landsberg, JM||Schenck, Hal||Weyman, Jerzy

publication date

• January 2018

publisher

• Elsevier  Publisher

published in

• Journal of Algebra  Journal

keywords

• Computational Complexity
• Determinant
• Free Resolution
• Permanent

Digital Object Identifier (DOI)

• 10.1016/j.jalgebra.2018.01.021

start page

• 8

end page

• 20

volume

• 503

URL

• http://dx.doi.org/10.1016/j.jalgebra.2018.01.021