Inspiriert von dieser Frage und insbesondere dem letzten Absatz von Ors Antwort, habe ich folgende Frage:
Kennen Sie Anwendungen der Darstellungstheorie der symmetrischen Gruppe in TCS?
Die symmetrische Gruppe ist die Gruppe aller Permutationen von mit Gruppenoperationszusammensetzung. Eine Darstellung von ist ein Homomorphismus von zu der allgemeinen linearen Gruppe von invertierbaren komplexen Matrizen. Eine Repräsentation wirkt durch Matrixmultiplikation auf . Eine irreduzible Darstellung von ist eine Aktion, die keinen richtigen Unterraum von invariant lässt. Irreduzible Darstellungen endlicher Gruppen erlauben es, eine Fourier-Transformation über nicht-abelsche Gruppen zu definieren { 1 , … , n } S n S n n × n C n S n C n. Diese Fourier-Transformation teilt einige der schönen Eigenschaften der diskreten Fourier-Transformation über zyklische / abelsche Gruppen. Beispielsweise wird die Faltung auf der Fourier-Basis zur punktweisen Multiplikation.
Die Darstellungstheorie der symmetrischen Gruppe ist wunderbar kombinatorisch. Jede irreduzible Darstellung von entspricht einer ganzzahligen Partition von . Hat diese Struktur und / oder die Fouriertransformation über die symmetrische Gruppe irgendeine Anwendung in TCS gefunden? n
quelle
Antworten:
Hier sind einige andere Beispiele.
Diaconis und Shahshahani (1981) untersuchten, wie viele zufällige Transpositionen erforderlich sind, um eine nahezu gleichmäßige Permutation zu erzeugen. Sie zeigten eine scharfe Schwelle von 1/2 n log (n) +/- O (n). Erzeugen einer zufälligen Permutation mit zufälligen Transpositionen .
Kassabov (2005) hat bewiesen, dass man auf der symmetrischen Gruppe einen begrenzten Gradexpander aufbauen kann. Symmetrische Gruppen und Expandergraphen .
Kuperberg, Lovett und Peled (2012) haben bewiesen, dass es kleine Mengen von Permutationen gibt, die gleichmäßig auf k-Tupel wirken. Probabilistische Existenz starrer kombinatorischer Strukturen .
quelle
Eine sehr gute Frage. Ich kenne die vollständige Antwort nicht und würde sie gerne selbst erfahren. Möglicherweise finden Sie jedoch Folgendes interessant. Betrachten wir statt der Gruppe ihr 0-Hecke-Monoid , so liegt eine Repräsentation auf einer bestimmten Klasse ganzzahliger Matrizen vor, die durch tropische -Multiplikation wirkt. Dies hat eine Menge interessanter Anwendungen in der Stringologie, und zwar über kürzeste Wege mit mehreren Quellen in gitterartigen Graphen. Einzelheiten finden Sie in meinem technischen Bericht:Sn H0(Sn) (min,+)
A. Tiskin. Semi-lokaler Stringvergleich: Algorithmische Techniken und Anwendungen. http://arxiv.org/abs/0707.3619
quelle
Hier ist ein Beispiel, das ich kenne:
"Über die" Log-Rank " -Vermutung in Kommunikationskomplexität" , R.Raz, B.Spieker,
Ich glaube das gibt noch viel mehr.
quelle
Hier ist ein Beispiel aus dem Quantencomputing:
Sie zeigen, dass die Quantenabfragekomplexität eines bestimmten Problems mit der Bezeichnung Index Erasure wobei die Darstellungstheorie der symmetrischen Gruppe verwendet wird, um eine optimale Gegnermatrix zu konstruieren, die sich in die Quantengegnermethode einfügt.Ω(n−−√)
quelle
Knuths dritter Band der Art of Computer Programming widmet sich dem Suchen und Sortieren sowie der Kombinatorik und den Permutationen und der Robinson-Schensted-Knuth-Korrespondenz , die in der Darstellungstheorie der symmetrischen Gruppe von zentraler Bedeutung ist.
Es gibt mehrere Arbeiten von Ellis-Friedgut-Pilpel und Ellis-Friedgut-Filmus, die extreme kombinatorische Probleme mit Hilfe der Harmonischenanalyse an lösen . Nicht ganz TCS, aber ganz in der Nähe.Sn
Ajtai hatte in den frühen 90er Jahren wunderbare Ergebnisse zur modularen Darstellung von die durch Fragen der rechnerischen Komplexität motiviert waren. Ich erinnere mich nicht an die Details oder ob sie veröffentlicht wurden, aber das ist es wert, durchgesehen zu werden!Sn
quelle
Die symmetrische Gruppe trotzt starker Fourier-Abtastung von Moore, Russell, Schulman
"Wir zeigen, dass das Problem der versteckten Untergruppen über der symmetrischen Gruppe nicht effizient durch eine starke Fourier-Abtastung gelöst werden kann ... Diese Ergebnisse gelten für den Sonderfall, der für das Graphisomorphismus-Problem relevant ist."
mit einer Verbindung zur Lösung des Graph-Isomorphismus-Problems über QM-Ansätze
sek 5 Darstellungstheorie der symmetrischen Gruppe
quelle
Mehr Statistik als Informatik, aber dennoch interessant: In Kapitel 8 der Monographie von Diaconis zu Gruppenpräsentationen in Wahrscheinlichkeit und Statistik werden Spektralanalysetechniken für Daten entwickelt, die mit einer Gruppe assoziiert sind. Dies erweitert die klassische Spektralanalyse von Zeitreihendaten, wobei das natürliche der Real oder die Ganzzahlen sind, die hinzugefügt werden. Es ist sinnvoll, als wenn Daten durch Rangfolgen angegeben werden. Die Monographie geht auf die Interpretation der Fourier-Koeffizienten von Rangdaten ein. In diesem Fall wird der Datensatz durch ein spärlichesG G S n f : S n → R +G G G Sn f:Sn→R+ Hiermit wird die Rangfolge (durch eine Permutation vorgegeben) dem Bevölkerungsanteil zugeordnet, der die Rangfolge bevorzugt.
Ebenfalls im selben Kapitel wird die Fourier-Analyse über die symmetrischen und anderen Gruppen verwendet, um ANOVA-Modelle und -Tests abzuleiten.
Eine natürliche Erweiterung davon wäre die statistische Lerntheorie für Rangordnungsprobleme, die von repräsentationstheoretischen Techniken in ähnlicher Weise profitiert, wie die Lerntheorie für die binäre Klassifikation unter der gleichmäßigen Verteilung von der Fourier-Analyse des Booleschen Würfels profitiert hat.
quelle
Die Darstellungstheorie der symmetrischen Gruppe spielt eine Schlüsselrolle im Ansatz der Geometrischen Komplexitätstheorie für Untergrenzen der Determinante oder der Matrixmultiplikation.
Bürgisser und Ikenmeyer beweisen mit der Darstellungstheorie von eine Untergrenze für den Randrang der Matrixmultiplikation .Sn
Wie sich die Darstellungstheorie von auf Untergrenzen der Determinante bezieht, erfahren Sie unter Geometrische Komplexitätstheorie II: Auf dem Weg zu expliziten Hindernissen für Einbettungen zwischen Klassensorten und Geometrische Komplexitätstheorie VI: Der Flip via PositivitätSn
quelle
Huangs-Doktorarbeit, PROBABILISTISCHE BEGRÜNDUNG UND LERNEN ÜBER PERMUTATIONEN: Ausnutzung struktureller Zerlegungen der symmetrischen Gruppe . Die Anwendung ist "ein echtes kamerabasiertes Tracking-Szenario für mehrere Personen".
Fouriertheoretische probabilistische Inferenz über Permutationen von Huang, Guestrin, Guibas; Journal of Machine Learning Research 10 (2009) 997-1070. siehe zB Abschnitt 5. Darstellungstheorie auf der symmetrischen Gruppe
ein weiteres Multitracking-Antragspapier. Multi-Objekt-Tracking mit Darstellungen der symmetrischen Gruppe (2007) von Kondor, Howard, Jebara
Lernwahrscheinlichkeitsverteilungen über Permutationen mittels Fourierkoeffizienten, Irurozki, Calvo, Lozano (Abt. CS / AI). siehe Abschnitt 2 Die Fourier-Transformation für die symmetrische Gruppe
quelle
Anwendung der Darstellungstheorie symmetrischer Gruppen zur Berechnung chromatischer Polynome von Graphen nach Klin und Pech
quelle
In dieser von Beals 1997 zitierten Veröffentlichung scheint STOC zu beweisen, dass die Quantenberechnung von Fourier-Transformationen über symmetrische Gruppen in BQP (Quantenpolynomialzeit) erfolgt
quelle
Ein älteres Beispiel, das sich jedoch noch in der jüngsten / laufenden Forschung befindet. Ein Teil dieser Theorie taucht in der Mathematik des "perfekten Shuffle" auf , das als Element der symmetrischen Gruppe angesehen wurde und zu dieser Zeit eine berühmte Entdeckung war. [1] erwähnt Anwendungen des Perfect Shuffle für Parallelverarbeitungsalgorithmen sowie die Verbindung zu Cooley-Tukey O (n log n) DFT. [2] ist neuer. Die perfekte Mischung zeigt sich in Parallelverarbeitung [3], Speicherdesign und Sortiernetzwerken.
[1] Mathematik des perfekten Mischens von Diaconis, Graham, Cantor. 1983
[2] Zyklen der Multiway Perfect Shuffle Permutation von Ellis, Fan, Shallit (2002)
[3] Parallelverarbeitung mit dem perfekten Shuffle von Stone, 1971
[4] Omega-Netzwerk basierend auf perfektem Mischen
[5] Paralleles und sequentielles In-Place-Permutieren und perfektes Mischen mithilfe von Involutionen Yang et al. (2012)
quelle