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