Zastosowania teorii reprezentacji grupy symetrycznej

42

Zainspirowany tym pytaniem, a w szczególności ostatnim akapitem odpowiedzi Or, mam następujące pytanie:

Czy znasz jakieś zastosowania teorii reprezentacji grupy symetrycznej w TCS?

Grupa symetryczna $S_n$ jest grupą wszystkich permutacji $\{1, \ldots, n\}$ o składzie operacji grupowych. Przedstawienie $S_n$ jest homomorfizmem z $S_n$ ogólnej grupy liniowego odwracalnych $n \times n$ złożonych macierzy. Reprezentacja działa na $\mathbb{C}^n$ przez mnożenie macierzy. Nieredukowalna reprezentacja $S_n$ jest działaniem, które nie pozostawia właściwej podprzestrzeni niezmiennika $\mathbb{C}^n$ . Nieredukowalne reprezentacje grup skończonych pozwalają zdefiniować aTransformacja Fouriera w grupach nie-abelowych . Ta transformata Fouriera ma kilka miłych właściwości dyskretnej transformaty Fouriera w grupach cyklicznych / abelowych. Na przykład splot staje się mnożeniem punktowym w podstawie Fouriera.

Teorii reprezentacji grupy symetrycznej jest pięknie kombinatorycznej. Każda nieredukowalna reprezentacja $S_n$ odpowiada całkowitej liczbie $n$ . Czy ta struktura i / lub transformata Fouriera w grupie symetrycznej znalazła jakąkolwiek aplikację w TCS?

co.combinatorics permutations fourier-analysis gr.group-theory Sasho Nikolov
źródło

patrz także zastosowania grupy symetrycznej , wikipedia

vzn

wszystkie bardzo interesujące odpowiedzi. Trudno mi będzie wybrać jedną do zaakceptowania.

Sasho Nikolov,

przyzwoite, czysto teoretyczne wprowadzenie / przegląd, Young Tableaux and the Representations of the Symmetric Group, autor: Zhao

vzn

2

Ten artykuł właśnie uderzył w kwantowy arXiv: rozwiązanie typowości dwóch stron przy użyciu teorii reprezentacji grupy symetrycznej autorstwa Janisa Noetzela.

Tyson Williams,

Faktoryzacja macierzy oparta na symetrii autorstwa Egnera i Puschela wykorzystuje elementy teorii

i reprezentacji do wydajnego rozkładania / rozkładania / mnożenia macierzy. patrz S3.2 na temat symetrii Perm-Perm.

S_{n}

$S_n$

vzn

27

Oto kilka innych przykładów.

Diaconis i Shahshahani (1981) badali, ile losowych transpozycji jest wymaganych do wygenerowania prawie jednolitej permutacji. Okazały się one ostrym progiem 1/2 n log (n) +/- O (n). Generowanie losowej permutacji z losowymi transpozycjami .
Kassabov (2005) udowodnił, że można zbudować ekspander ograniczonego stopnia na grupie symetrycznej. Grupy symetryczne i wykresy ekspanderów .
Kuperberg, Lovett i Peled (2012) udowodnili, że istnieją małe zestawy permutacji, które działają jednolicie na k-krotki. Probabilistyczne istnienie sztywnych struktur kombinatorycznych .

Shachar Lovett
źródło

3

Dzięki Shachar i witamy w cstheory! Pozwoliłem sobie naprawić twoje linki: były trochę niedopasowane

Sasho Nikolov

14

$S_n$ $H_0(S_n)$ $(\min,+)$

A. Tiskin. Pół-lokalne porównanie ciągów: techniki i zastosowania algorytmiczne. http://arxiv.org/abs/0707.3619

Alexander Tiskin
źródło

Dziękuję Ci! Wygląda to bardzo interesująco i na pewno to sprawdzę.

Sasho Nikolov,

14

Oto jeden przykład, który znam:

`` O hipotezie log-rank 'w złożoności komunikacyjnej' ' , R.Raz, B.Spieker,

Proceeding of the 34th FOCS, 1993, pp. 168-177
Combinatorica 15(4) (1995) pp. 567-588

Wierzę, że jest o wiele więcej.

Klim
źródło

3

Czy mógłbyś podsumować, jakie modele reprezentacji i jak są stosowane?

Vijay D

@VijayD zapewne Klim wie więcej, ale problemem jest tutaj złożoność komunikacji funkcji jest związany z logem jego rangi (myśląc o jako macierzy rzeczywistej ). Konstruują rangi i CC . Ranga jest obliczana przez zapisanie jej jako sumy macierzy w regularnej reprezentacji

f : {0, 1}^{n} \times {0, 1}^{n} \to {0, 1}

$f:\{0,1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$

f

$f$

2^{d} \times 2^{d}

$2^d \times 2^d$

f

$f$

2^{O (n)}

$2^{O(n)}$

Ω (n \log \log n)

$\Omega(n \log \log n)$

f

$f$

S_{n}

$S_n$

Sasho Nikolov

Właściwie czytałem ten artykuł jakiś czas temu, więc teraz nie pamiętam go dokładnie.

Klim

11

Oto przykład z obliczeń kwantowych:

Roland, Jeremie; Roetteler, Martin; Magnin, Loïck; Ambainis, Andris (2011), „Symmetry Assisted Adversaries for Quantum State Generation”, Materiały z 26. dorocznej konferencji IEEE 2011 na temat złożoności obliczeniowej, CCC '11, IEEE Computer Society, s. 167–177, doi: 10.1109 / CCC. 2011.24

Pokazują one, że kwantowa złożoność kwerendy określonego problemu o nazwie Skasowanie indeksu to wykorzystując teorię reprezentacji grupy symetrycznej do skonstruowania optymalnej macierzy przeciwników, aby podłączyć ją do kwantowej metody przeciwnika. $\Omega(\sqrt{n})$

Robin Kothari
źródło

10

Trzeci tom „Sztuki programowania komputerowego” Knuth poświęcony jest wyszukiwaniu i sortowaniu oraz poświęca wiele na kombinatorykę i permutacje oraz korespondencję Robinsona-Schensteda-Knutha , która jest centralną częścią teorii reprezentacji grupy symetrycznej.
Istnieje kilka artykułów Ellis-Friedgut-Pilpel i Ellis-Friedgut-Filmus, które rozwiązują ekstremalne problemy kombinatoryczne za pomocą analizy harmonicznej na . Nie całkiem TCS, ale całkiem blisko. $S_n$
Ajtai miał na początku lat 90-tych wspaniałe wyniki w modułowej reprezentacji które były motywowane pytaniami o złożoności obliczeniowej. Nie pamiętam szczegółów ani tego, czy zostały opublikowane, ale warto to przejrzeć! $S_n$

Gil Kalai
źródło

Dzięki Gil! Uważam, że jednym z artykułów Ajtaja, który masz na myśli, jest ten: eccc.hpi-web.de/eccc-reports/1994/TR94-015/index.html . Myślę, że zastosowanie ma dowód złożoności zasady szuflady, ale nie do końca rozumiem związek.

Sasho Nikolov

6

Grupa symetryczna przeciwstawia się silnemu próbkowaniu Fouriera przez Moore'a, Russella, Schulmana

„pokazujemy, że problemu ukrytej podgrupy w grupie symetrycznej nie można skutecznie rozwiązać za pomocą silnego próbkowania Fouriera… Te wyniki dotyczą specjalnego przypadku związanego z problemem izomorfizmu grafów”.

z powiązaniem z rozwiązaniem problemu izomorfizmu grafów poprzez podejście QM

ust. 5 Teoria reprezentacji grupy symetrycznej

vzn
źródło

5

Nadal interesujący więcej statystyk niż informatyce, ale: W rozdziale 8 monografii Diaconis' na grupowe Gepresentations prawdopodobieństwa i statystyki , widmowe techniki analizy dla danych związanych z grupą są rozwinięte. To rozszerza bardziej klasyczną analizę spektralną danych powiedzmy szeregów czasowych, gdzie naturalnym są liczby rzeczywiste lub liczby całkowite. Sensowne jest przyjmowanie jako gdy dane są podawane w rankingach. Monografia zajmuje się interpretacją współczynników Fouriera rankingu danych. W takim przypadku zbiór danych jest reprezentowany przez rzadki $G$ $G$ $G$ $S_n$ $f:S_n \rightarrow \mathbb{R}^+$ który mapuje rankingi (nadane przez permutację) do części populacji, która preferuje ranking.

Również w tym samym rozdziale wykorzystano analizę Fouriera w symetrycznych i innych grupach do uzyskania modeli i testów ANOVA.

Naturalnym rozszerzeniem tego zjawiska byłaby statystyczna teoria uczenia się do rangowania problemów korzystających z technik reprezentacyjnych w sposób podobny do sposobu, w jaki teoria uczenia się do klasyfikacji binarnej w rozkładzie równomiernym skorzystała z analizy Fouriera na kostce boolowskiej.

Sasho Nikolov
źródło

Jaka jest jednak naturalna struktura grupy dla problemów z rankingiem?

Suresh Venkat

1

@Suresh Miałem na myśli grupę symetryczną, ale mój ostatni akapit to bardziej pobożne życzenia niż cokolwiek innego. Miałem na myśli problem podobny do junty w rankingach: uczenie się funkcji która zależy od względnego uporządkowania tylko kilku elementów z kilku próbek. Być może techniki czterokierunkowe mogą dać nietrywialne granice dla próbek

f : S_{n} \to {0, 1}

$f:S_n \rightarrow \{0, 1\}$

[n]

$[n]$

Sasho Nikolov,

5

Teoria reprezentacji grupy symetrycznej odgrywa kluczową rolę w podejściu teorii złożoności geometrycznej do dolnych granic wyznacznika lub mnożenia macierzy.

Bürgisser i Ikenmeyer dowodzą dolnej granicy granicy mnożenia macierzy za pomocą teorii reprezentacji . $S_n$
Aby dowiedzieć się, jak teoria reprezentacji odnosi się do dolnych granic wyznacznika, zobacz Teoria złożoności geometrycznej II: W kierunku wyraźnych przeszkód dla osadzenia między odmianami klas i teoria złożoności geometrycznej VI: via ip poprzez dodatni $S_n$

Joshua Grochow
źródło

4

Praca doktorska Huangsa, PROBABILISTYCZNE POWODOWANIE I NAUKA ZEZWOLEŃ: wykorzystanie rozkładów strukturalnych grupy symetrycznej . aplikacja to „oparty na kamerze scenariusz śledzenia wielu osób”.
Teoretyczna wnioskowanie probabilistyczne Fouriera o permutacjach Huanga, Guestrina, Guibasa; Journal of Machine Learning Research 10 (2009) 997-1070. patrz np. pkt 5. Teoria reprezentacji w grupie symetrycznej
kolejny papier do aplikacji wielościeżkowych. Śledzenie wielu obiektów z reprezentacjami grupy symetrycznej (2007) autorstwa Kondora, Howarda, Jebary
Uczenie się rozkładów prawdopodobieństwa dla permutacji za pomocą współczynników Fouriera, Irurozki, Calvo, Lozano (Dept CS / AI). patrz ust. 2 Przekształcenie Fouriera w grupie symetrycznej

vzn
źródło

1

Sugeruję połączenie tej odpowiedzi z innym odniesieniem do permutacji do nauki

Sasho Nikolov,

ok ... łączenie ...

dniu

patrz także Interpretacja spektrum fazowego w analizie Fouriera danych częściowego rankingu i Podejście przetwarzania sygnału do analizy Fouriera danych rankingu: znaczenie fazy Kakarali, która wydaje się rozszerzać znacznie wcześniejszą pracę Diaconisa

dniu

-1

Zastosowanie teorii reprezentacji grup symetrycznych do obliczania wielomianów chromatycznych wykresów przez Klin i Pech

vzn
źródło

aplikacja

ps—

-2

ten wysoce cytowany artykuł Bealsa, 1997, STOC wydaje się dowodzić, że obliczenia kwantowe transformacji Fouriera w grupach symetrycznych są w BQP, tj. kwantowym czasie wielomianowym

vzn
źródło

2

to samo dotyczy drugiego papieru kwantowego, do którego się odnosi. główną motywacją do opracowania nieabelowej transformacji Fouriera było wykorzystanie jej do rozwiązania problemu ukrytej podgrupy w grupie symetrycznej. drugi cytowany artykuł pokazuje, że takie podejście nie rozwiązuje problemu.

Sasho Nikolov,

btw, żeby być jasnym: co mam na myśli z powyższym komentarzem, to sugerowanie połączenia tej odpowiedzi z drugą odpowiedzią QM i wyjaśnienie, w jaki sposób są one powiązane (ponieważ są)

Sasho Nikolov

ok Moore i wsp. przytaczają Beals, chociaż nie tak znalazłem papier Beals. może scalić się później, ale teraz niektórym odbiorcom nie podoba się ten ref Beals z jakiegokolwiek powodu (stary, zastąpiony itp ...?)

dniu

nie jestem pewien, myślę, że jest to dobre odniesienie. Jednym z problemów jest dla mnie to, że nie wyjaśniacie, dlaczego ważna jest możliwość obliczenia nieabelowej transformacji Fouriera, w jaki sposób jest ona motywowana.

Sasho Nikolov,

1

wolałbym, aby odpowiedzi same w sobie dawały czytelnikowi wystarczającą wskazówkę, aby mógł zdecydować, czy przeczytać cały artykuł, czy nie. chciałbym, aby odpowiedź była czymś więcej niż tylko powierzchownym zrozumieniem materiału.

Sasho Nikolov,

-5

starszy przykład, ale wciąż z najnowszymi / trwającymi badaniami, część tej teorii pojawia się w matematyce „idealnego tasowania” , postrzeganego jako element grupy symetrycznej i który był wówczas znanym odkryciem. [1] wspomina o zastosowaniach idealnego tasowania algorytmów przetwarzania równoległego, a także o połączeniu z Cooley-Tukey O (n log n) DFT. [2] jest nowszy. idealne odtwarzanie losowe pojawia się przy przetwarzaniu równoległym [3], projektowaniu pamięci i sortowaniu sieci.

[1] Matematyka idealnego tasowania Diaconisa, Grahama, Cantora. 1983

[2] Cykle wielo-doskonałej permutacji shuffle autorstwa Ellis, Fan, Shallit (2002)

[3] Równoległe przetwarzanie z doskonałym tasowaniem Stone'a, 1971

[4] Sieć Omega oparta na perfekcyjnym tasowaniu

[5] Równoległe i sekwencyjne permutowanie w miejscu i idealne tasowanie przy użyciu inwolucji Yang i in. (2012)

vzn
źródło

1

Czy w tych pracach stosowana jest teoria reprezentacji?

Sasho Nikolov,

wydaje się być szczególnym przypadkiem nim

vzn

2

co jest szczególnym przypadkiem czego? idealne odtwarzanie losowe to permutacja. pytam, czy teoria reprezentacji jest używana w dowodach w tych dokumentach? nie znalazłem żadnego.

Sasho Nikolov

3

w przeciwnym razie istnieją probabilistyczne modele (niedoskonałego) tasowania, a powtarzane tasowanie przy użyciu jednego z tych modeli jest przypadkowym przejściem na permutacje. czasami można analizować czas mieszania takiego losowego marszu, stosując analizę Fouriera na grupie symetrycznej: Shachar podał jeden przykład losowego losowania transpozycji. twoje referencje są interesujące, ale nie widzę żadnego związku z teorią reprezentacji: prace dotyczą kilku (dwóch w [1]) deterministycznych przetasowań i grup permutacji, które generują. analiza wydaje się być kombinatoryjna

Sasho Nikolov

niedoskonałe tasowanie jest również interesujące, ale cały pt odpowiedzi jest tasowaniem idealnym. wydaje się, że powyższe same wyniki mogą zostać przekształcone lub udowodnione za pomocą teorii reprezentacji lub wykorzystują niektóre jej kluczowe aspekty bez oczywistych / bezpośrednich odniesień do nich. Uwaga Shachars odpowiedź cytuje Diaconis, tego samego autora w jednym z artykułów w tej odpowiedzi. innymi słowy, powyżsi autorzy z pewnością mogliby lepiej odpowiedzieć na twoje pytanie, ale oczekuję, że odpowiedzą przynajmniej nieco twierdząco =) ... poza tym właśnie opisałeś teorię reprezentacji jako „pięknie kombinatoryczną” we własnym pytaniu!

vzn

Zastosowania teorii reprezentacji grupy symetrycznej

Odpowiedzi: