2015/05/08 by Alper, Jarod, Bogart, Tristram, Velasco, Mauricio
#14M12 #68Q05 #68Q17 #Algebraic Geometry (math.AG) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1505.02205
We prove that the determinantal complexity of a hypersurface of degree d > 2 is bounded below by one more than the codimension of the singular locus, provided that this codimension is at least 5. As a result, we obtain that the determinantal complexity of the 3 × 3 permanent is 7. We also prove that for n> 3, there is no nonsingular hypersurface in Pn of degree d that has an expression as a determinant of a d × d matrix of linear forms while on the other hand for n ≤ 3, a general determinantal expression is nonsingular. Finally, we answer a question of Ressayre by showing that the determinantal complexity of the unique (singular) cubic surface containing a single line is 5.