Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Geometric complexity theory and matrix powering   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.

25
The categories of this paper are: patt-sol
13
The categories of this paper are: quant-ph
28
The categories of this paper are: alg-geom
34
The categories of this paper are: chem-ph
7
The categories of this paper are: hep-th
10
The categories of this paper are: q-bio
12
The categories of this paper are: nucl-th
22
The categories of this paper are: chao-dyn
3
The categories of this paper are: physics
23
The categories of this paper are: solv-int
15
The categories of this paper are: nucl-ex
21
The categories of this paper are: adap-org
5
The categories of this paper are: gr-qc
4
The categories of this paper are: cond-mat
32
The categories of this paper are: atom-ph
26
The categories of this paper are: bayes-an