Zastosowania teorii reprezentacji grupy symetrycznej

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?

Oto kilka innych przykładów.

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

2. Kassabov (2005) udowodnił, że można zbudować ekspander ograniczonego stopnia na grupie symetrycznej. Grupy symetryczne i wykresy ekspanderów .

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

$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

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.

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})$

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

2. 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$

3. 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$

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

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 rzadkiG G S n f : S n → R$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.

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$

• 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

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

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

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)