Applications de la théorie de la représentation du groupe symétrique

42

Inspiré par cette question et en particulier par le dernier paragraphe de la réponse de Ou, j'ai la question suivante:

Connaissez-vous des applications de la théorie de la représentation du groupe symétrique dans TCS?

Le groupe symétrique est le groupe de toutes les permutations de avec une composition d'opération de groupe. Une représentation de S_n est un homomorphisme de S_n au groupe linéaire général des matrices complexes n \ fois n inversibles. Une représentation agit sur \ mathbb {C} ^ n par multiplication de matrice. Une représentation irréductible de S_n est une action qui ne laisse aucun sous-espace propre de \ mathbb {C} ^ n invariant. Les représentations irréductibles de groupes finis permettent de définir une transformation de Fourier sur des groupes non abéliensSn{1,,n}SnSnn×nCnSnCn. Cette transformée de Fourier partage certaines des propriétés intéressantes de la transformée de Fourier discrète sur les groupes cycliques / abéliens. Par exemple, la convolution devient une multiplication ponctuelle dans la base de Fourier.

La théorie de la représentation du groupe symétrique est magnifiquement combinatoire. Chaque représentation irréductible de Sn correspond à une partition entière de n . Cette structure et / ou la transformation de Fourier sur le groupe symétrique ont-elles trouvé une application dans TCS?

Sasho Nikolov
la source
voir aussi les applications du groupe symétrique , wikipedia
vzn
toutes les réponses très intéressantes. Je vais avoir du mal à choisir celui qui accepte.
Sasho Nikolov
décent Introduction / vue purement théorique, jeune et les représentations Tableaux du Groupe Symétrique, par Zhao
VZN
2
Cet article vient tout juste de commencer par la quant-ph arXiv: une solution à la typicité à deux partis utilisant la théorie de la représentation du groupe symétrique de Janis Noetzel.
Tyson Williams
La factorisation matricielle basée sur la symétrie par Egner et Puschel utilise des éléments de et la théorie de la représentation pour une factorisation / décomposition / multiplication matricielle efficace. voir S3.2 sur la symétrie Perm-Perm. Sn
vzn

Réponses:

27

Voici quelques autres exemples.

  1. Diaconis et Shahshahani (1981) ont étudié le nombre de transpositions aléatoires nécessaires pour générer une permutation presque uniforme. Ils ont prouvé un seuil net de 1/2 n log (n) +/- O (n). Générer une permutation aléatoire avec des transpositions aléatoires .

  2. Kassabov (2005) a prouvé qu'il est possible de construire un expandeur de degrés borné sur le groupe symétrique. Groupes symétriques et graphiques d’expansion .

  3. Kuperberg, Lovett et Peled (2012) ont prouvé qu'il existait de petits ensembles de permutations qui agissent uniformément sur les k-tuples. Existence probabiliste de structures combinatoires rigides .

Shachar Lovett
la source
3
Merci Shachar, et bienvenue à cstheory! J'ai pris la liberté de réparer vos liens: ils étaient un peu incompatibles
Sasho Nikolov
14

Une très bonne question. Je ne connais pas la réponse complète et voudrais le savoir moi-même. Cependant, vous pouvez trouver ce qui suit intéressant. Si, au lieu du groupe , nous considérons son monoïde 0-Hecke , il a une représentation sur une certaine classe de matrices entières qui agit par multiplication tropicale . Cela a beaucoup d'applications intéressantes en stringologie, via les plus courts chemins multi-sources dans des graphes en forme de grille. Pour plus de détails, voir mon rapport technique:SnH0(Sn)(min,+)

A. Tiskin. Comparaison de chaînes semi-locale: techniques algorithmiques et applications. http://arxiv.org/abs/0707.3619

Alexander Tiskin
la source
Merci! Cela semble très intéressant et je vais certainement le vérifier.
Sasho Nikolov
14

Voici un exemple que je connais:

`` Sur la conjecture 'Log-Rank' dans la complexité de la communication '' , R.Raz, B.Spieker,

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

Je crois qu'il y a beaucoup plus.

Klim
la source
3
Pourriez-vous résumer ce que les modèles de représentation et comment il est appliqué?
Vijay D
@VijayD Klim en sait probablement plus, mais le problème est de savoir comment la complexité de la communication d’une fonction est lié au log de son rang (en considérant comme une matrice réelle ). Ils construisent un de rang et CC . Le rang de est calculé en l'écrivant sous la forme de la somme des matrices dans la représentation régulière def:{0,1}n×{0,1}n{0,1}f2d×2df2O(n)Ω(nloglogn)fSn
Sasho Nikolov
En fait, j’ai lu ce document il ya un certain temps, alors je ne me souviens pas exactement de cela.
Klim
11

Voici un exemple tiré de l'informatique quantique:

Roland, Jérémie; Roetteler, Martin; Magnin, Loïck; Ambainis, Andris (2011), "Adversaires assistés par symétrie pour la génération d'états quantiques", Actes de la 26e conférence annuelle de l'IEEE sur la complexité informatique, CCC '11, IEEE Computer Society, p. 167–177, doi: 10.1109 / CCC. 2011.24

Ils montrent que la complexité de la requête quantique d'un certain problème appelé Index Erasure est utilisant la théorie de la représentation du groupe symétrique pour construire une matrice d'adversaire optimale à intégrer à la méthode d'adversaire quantique.Ω(n)

Robin Kothari
la source
10
  1. Le troisième volume de Knuth, intitulé The Art of Computer Programming, est consacré à la recherche et au tri. Il est consacré à la combinatoire et aux permutations ainsi qu’à la correspondance de Robinson-Schensted-Knuth , élément central de la théorie de la représentation du groupe symétrique.

  2. Ellis-Friedgut-Pilpel et Ellis-Friedgut-Filmus décrivent plusieurs problèmes qui résolvent des problèmes combinatoires extrêmes au moyen de l'analyse harmonique sur . Pas tout à fait TCS, mais assez proche.Sn

  3. Au début des années 90, Ajtai a obtenu d’excellents résultats sur la représentation modulaire de motivés par des questions de complexité de calcul. Je ne me souviens pas des détails ou si cela a été publié, mais cela vaut la peine de le parcourir!Sn

Gil Kalai
la source
Merci Gil! Je pense que l’un des articles d’Ajtaj que vous avez à l’esprit est celui-ci: eccc.hpi-web.de/eccc-reports/1994/TR94-015/index.html . Je pense que l'application est à la complexité de preuve du principe de casier, mais je ne comprends pas encore le lien.
Sasho Nikolov
6

Le groupe symétrique défie le fort échantillonnage de Fourier par Moore, Russell et Schulman

"Nous montrons que le problème de sous-groupe caché sur le groupe symétrique ne peut pas être résolu efficacement par un échantillonnage fort de Fourier ... Ces résultats s'appliquent au cas particulier relatif au problème de l'isomorphisme de graphes."

avec une connexion pour résoudre le problème de l'isomorphisme de graphes via des approches de gestion de la qualité

sec 5 Théorie de la représentation du groupe symétrique

vzn
la source
5

Plus de statistiques que d’informatique, mais toujours intéressantes: au chapitre 8 de la monographie de Diaconis sur la représentation des groupes en probabilité et statistique , des techniques d’analyse spectrale des données associées à un groupe sont développées. Cela étend l’analyse spectrale plus classique de données de séries chronologiques dites, où le naturel est le réel ou le nombre entier sous addition. Il est logique de prendre comme lorsque les données sont données par les classements. La monographie interprète les coefficients de Fourier des données de classement. Dans ce cas, le jeu de données est représenté par une lettreGGGSnf:SnR+ qui mappe les classements (donnés par une permutation) à la fraction de la population qui préfère le classement.

Toujours dans le même chapitre, l'analyse de Fourier sur les groupes symétriques et autres est utilisée pour dériver des modèles et des tests ANOVA.

Une extension naturelle de ceci serait la théorie statistique d’apprentissage pour classer les problèmes qui bénéficient des techniques théoriques de représentation d’une manière similaire à la façon dont la théorie théorique pour la classification binaire sous la distribution uniforme a bénéficié de l’analyse de Fourier sur le cube booléen.

Sasho Nikolov
la source
Quelle est la structure naturelle du groupe pour classer les problèmes?
Suresh Venkat le
1
@Suresh J'avais en tête le groupe symétrique, mais mon dernier paragraphe évoque plus un voeu pieux qu'autre chose. Je pensais à un problème de classement semblable à celui de la junte: apprendre une fonction qui dépend du classement relatif de seulement quelques éléments de partir de quelques échantillons. Peut-être que les techniques de fourier peuvent donner des résultats non-triviauxf:Sn{0,1}[n]
Sasho Nikolov
5

La théorie de la représentation du groupe symétrique joue un rôle clé dans l'approche de la théorie de la complexité géométrique des limites inférieures du multiplicateur déterminant ou de la multiplication matricielle.

Joshua Grochow
la source
4
vzn
la source
1
Je suggère de fusionner cette réponse avec l'autre référence d'apprentissage
Sasho Nikolov
ok ... fusion ...
vzn
-2

Ce document très cité de Beals, 1997, STOC semble prouver que le calcul quantique de la transformation de Fourier sur des groupes symétriques est en BQP, c’est-à-dire en temps polynomial quantique.

vzn
la source
2
encore une fois cela va avec l'autre papier quantique que vous avez mentionné. La principale motivation du développement de la transformation de Fourier non abélienne était de l'utiliser pour résoudre le problème des sous-groupes cachés par rapport au groupe symétrique. L'autre document que vous citez montre que cette approche ne résout pas le problème.
Sasho Nikolov
Soyons clairs: ce que je veux dire par le commentaire ci-dessus est de suggérer de fusionner cette réponse avec l'autre réponse QM et d'expliquer comment les deux sont liés (parce qu'ils le sont)
Sasho Nikolov
ok Moore et al. citent Beals bien que ce ne soit pas comment j'ai trouvé le papier Beals. pourrait fusionner plus tard, mais pour le moment, certains publics ne semblent pas aimer cette référence de Beals pour quelque raison que ce soit (ancienne, remplacée, etc.??)
vzn
Je ne suis pas sûr, je pense que c'est une bonne référence. Un problème pour moi est que vous n'expliquez pas pourquoi il est important de pouvoir calculer la transformée de Fourier non abélienne, comment elle est motivée.
Sasho Nikolov
1
Je préférerais que les réponses soient indépendantes et donnent au lecteur un indice suffisant pour lui permettre de décider s'il doit lire l'intégralité du document ou non. Je voudrais que la réponse montre plus qu'une compréhension superficielle de la matière.
Sasho Nikolov
-5

un exemple plus ancien, mais toujours avec des recherches récentes / en cours, une partie de cette théorie apparaît dans les mathématiques du "mélange parfait" , considéré comme un élément du groupe symétrique & qui était une découverte célèbre à l'époque. [1] mentionne les applications du mélange parfait aux algorithmes de traitement parallèle ainsi que la connexion à Cooley-Tukey O (n log n) DFT. [2] est plus récent. le brassage parfait apparaît dans le traitement en parallèle [3], la conception de la mémoire et le tri des réseaux.

[1] Mathématiques du brassage parfait de Diaconis, Graham, Cantor. 1983

[2] Cycles de la permutation parfaite à plusieurs voies par Ellis, Fan, Shallit (2002).

[3] Traitement parallèle avec le brassage parfait réalisé par Stone, 1971.

[4] Réseau Omega basé sur un brassage parfait

[5] Permutation et permutation parfaite sur place parallèles et séquentielles en utilisant des involutions, Yang et al. (2012).

vzn
la source
1
La théorie de la représentation est-elle utilisée dans ces articles?
Sasho Nikolov
semble être un cas particulier
vzn
2
qu'est-ce qu'un cas particulier de quoi? le mélange parfait est une permutation. Je demande si la théorie de la représentation est utilisée dans les preuves de ces papiers? je n'en ai trouvé aucun.
Sasho Nikolov
3
sinon, il existe des modèles probabilistes de brassage (imparfait), et le brassage répété à l'aide de l'un de ces modèles est une marche aléatoire sur des permutations. on peut parfois analyser le temps de mélange d'une telle marche aléatoire en utilisant une analyse de Fourier sur le groupe symétrique: Shachar a donné un exemple pour le mélange aléatoire de transpositions. vos références sont intéressantes, mais je ne vois aucun lien avec la théorie de la représentation: les articles traitent de quelques remaniements déterministes (deux dans [1]) et des groupes de permutation qu’ils génèrent. l'analyse semble être combinatoire
Sasho Nikolov
Le brassage imparfait est intéressant aussi, mais le point entier de la réponse est le brassage parfait. Il semble que les mêmes résultats pourraient être repris ou prouvés via la théorie de la représentation ou en utiliser certains aspects essentiels sans référence évidente / directe. note Shachars répond cite Diaconis, même auteur sur l’un des papiers de cette réponse. en d'autres termes, les auteurs ci-dessus pourraient sûrement mieux répondre à votre question, mais je m'attendais à ce qu'ils répondent au moins un peu par l'affirmative =) ... en plus, vous venez de décrire la théorie de la représentation comme "magnifiquement combinatoire" dans votre propre question!
vzn