Geometric complexity theory and matrix powering

摘要: Valiant's famous determinant versus permanent problem is the flagship in algebraic complexity theory. Mulmuley and Sohoni (Siam J Comput 2001, 2008) introduced geometric theory, an approach to study this related problems via geometry representation Their works by multiplying polynomial with a high power of linear form (a process called padding) then comparing orbit closures padded permanent. This padding was recently used heavily show no-go results for method shifted partial derivatives (Efremenko, Landsberg, Schenck, Weyman, 2016) theory (Ikenmeyer Panova, FOCS 2016 Burgisser, Ikenmeyer 2016). Following classical homogenization result Nisan (STOC 1991) we replace trace variable matrix power. gives equivalent but much cleaner homogeneous formulation which removed. radically changes theoretic questions involved prove lower bounds. We that there are no occurrence obstructions even superlinear bounds on first rules out some model. Interestingly---in contrast determinant---the not uniquely determined its stabilizer.