Mulmuley och Sohoni [25, 26] föreslog att man skulle betrakta det permanenta kontra avgörande problemet som ett specifikt problem med att stänga banan och angripa det genom metoder från geometrisk invariant- och representationsteori. Vi antar dessa idéer mot målet att visa lägre gränser på gränsen rang av specifika tensorer, särskilt för matris multiplikation. Vi studerar således specifika banstängningsproblem för gruppen En nyckelidé från [26] är att de irreducible Gs-representationer som sker i koordinatringen av G-orbit stängning av en stabil tensor w  på W är exakt de som har en icke-noll invariant med avseende på stabilisatorgruppen av w. Vi bevisar dock att genom att överväga Gs-representationer, endast triviala lägre gränser på gränsen rang kan visas. Det är därför nödvändigt att studera G-representationer, vilket leder till problem med geometrisk utvidgning som ligger utanför ramen för de problem med begränsning av undergruppen som betonas i [25, 26] och dess uppföljningsdokument. Vi visar en mycket blygsam lägre gräns på gränsen rank av matris multiplikation tensorer med hjälp av G-representationer. Detta visar åtminstone att barriären för Gs-representationer kan övervinnas. För att avancera föreslår vi det grövre tillvägagångssättet att ersätta semigruppen av representationer av en tensor med dess ögonblick polytop. Vi bevisar de första resultaten mot att bestämma ögonblicket polytoper av matris multiplikation och unit tensorer. * En fullständig version av denna artikel finns på arxiv.org/abs/1011. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift.  Kategorier och ämnesdeskriptorer Algoritmer, Theory Nyckelord geometrisk komplexitet teori, tensor rank, matris multiplikation, banstängningar, multiplikationer, Kronecker koefficienter Vi tackar Matthias Christandl, Shrawan Kumar, Joseph Landsberg, Laurent Manivel, Ketan Mulmuley, och Jerzy Weyman för hjälpsamma diskussioner. Vi är tacksamma mot Fields Institute i Toronto för att ha skapat ett forum för att diskutera några frågor om GCT hösten 2009. Dessutom tackar vi Centre for Computational Intractability i Princeton för att ha möjliggjort workshopen i Geometric Complexity Theory 2010, där några av de resultat som presenteras här diskuterades.
Matris multiplikation tensor MM kännetecknas av dess symmetrier (t.ex., REF ).
Geometric complexity theory and tensor rank
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}