Geometric complexity theory and matrix powering

Publikation: Bidrag til tidsskriftTidsskriftartikelfagfællebedømt

Standard

Geometric complexity theory and matrix powering. / Gesmundo, Fulvio; Ikenmeyer, Christian; Panova, Greta.

I: Differential Geometry and its Applications, Bind 55, 2017, s. 106-127.

Publikation: Bidrag til tidsskriftTidsskriftartikelfagfællebedømt

Harvard

Gesmundo, F, Ikenmeyer, C & Panova, G 2017, 'Geometric complexity theory and matrix powering', Differential Geometry and its Applications, bind 55, s. 106-127. https://doi.org/10.1016/j.difgeo.2017.07.001

APA

Gesmundo, F., Ikenmeyer, C., & Panova, G. (2017). Geometric complexity theory and matrix powering. Differential Geometry and its Applications, 55, 106-127. https://doi.org/10.1016/j.difgeo.2017.07.001

Vancouver

Gesmundo F, Ikenmeyer C, Panova G. Geometric complexity theory and matrix powering. Differential Geometry and its Applications. 2017;55:106-127. https://doi.org/10.1016/j.difgeo.2017.07.001

Author

Gesmundo, Fulvio ; Ikenmeyer, Christian ; Panova, Greta. / Geometric complexity theory and matrix powering. I: Differential Geometry and its Applications. 2017 ; Bind 55. s. 106-127.

Bibtex

@article{f150202746f3492face65bd06179900e,
title = "Geometric complexity theory and matrix powering",
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.",
author = "Fulvio Gesmundo and Christian Ikenmeyer and Greta Panova",
year = "2017",
doi = "10.1016/j.difgeo.2017.07.001",
language = "English",
volume = "55",
pages = "106--127",
journal = "Differential Geometry and its Applications",
issn = "0926-2245",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Geometric complexity theory and matrix powering

AU - Gesmundo, Fulvio

AU - Ikenmeyer, Christian

AU - Panova, Greta

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

U2 - 10.1016/j.difgeo.2017.07.001

DO - 10.1016/j.difgeo.2017.07.001

M3 - Journal article

VL - 55

SP - 106

EP - 127

JO - Differential Geometry and its Applications

JF - Differential Geometry and its Applications

SN - 0926-2245

ER -

ID: 189700719