Determinantal Complexities and Field Extensions

Publication Type:
Conference Proceeding
LNCS - Algorithms and Computation - Proceedings of the 24th International Symposium, ISAAC 2013, 2013, 8283 pp. 119 - 129
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013005433OK.pdf255.5 kB
Adobe PDF
Let F be a field of characteristic ??2. The determinantal complexity of a polynomial P?F[x1,,xn] is defined as the smallest size of a matrix M whose entries are linear polynomials of x i s over F, such that P=det(M) as polynomials in F[x1,,xn]. To determine the determinantal complexity of the permanent polynomial is a long-standing open problem. Let K be an extension field of F; then P can be viewed as a polynomial over K. We are interested in the comparison between the determinantal complexity of P over K (denoted as dcK(P)), and that of P over F (denoted as dcF(P)). It is clear that dcK(P)=dcF(P), and the question is whether strict inequality can happen. In this note we consider polynomials defined over Q.
Please use this identifier to cite or link to this item: