Klim Efremenko
Senior Academic
On minimal free resolutions of sub-permanents and other ideals arising in complexity theory
We compute the linear strand of the minimal free resolution of the ideal generated by k×k sub-permanents of an n×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.
| Publication language | English |
| Pages | 8-20 |
| Journal | Journal of Algebra |
| Volume | 503 |
| Publication status | Published - 01.06.2018 |
Keywords
Computational complexity
Determinant
Free resolution
Permanent
ASJC Scopus subject areas
Algebra and Number Theory
