Aplicações da teoria das representações do grupo simétrico

42

Inspirado por esta pergunta e, em particular, pelo parágrafo final da resposta de Or, tenho a seguinte pergunta:

Você conhece alguma aplicação da teoria de representação do grupo simétrico no TCS?

O grupo simétrico é o grupo de todas as permutações de com a composição da operação do grupo. Uma representação de é um homomorfismo de para o grupo linear geral de matrizes complexas invertíveis . Uma representação atua em por multiplicação de matrizes. Uma representação irredutível de é uma ação que não deixa nenhum subespaço adequado de invariante. Representações irredutíveis de grupos finitos permitem definir uma transformação de Fourier sobre grupos não abelianos { 1 , , n } S n S n n × n C n S n C nSn{1,,n}SnSnn×nCnSnCn. Essa transformação de Fourier compartilha algumas das boas propriedades da transformação discreta de Fourier sobre grupos cíclicos / abelianos. Por exemplo, a convolução torna-se multiplicação pontual na base de Fourier.

A teoria da representação do grupo simétrico é maravilhosamente combinatória. Cada representação irredutível de corresponde a uma partição inteira de . Essa estrutura e / ou a transformação de Fourier sobre o grupo simétrico encontraram alguma aplicação no TCS? nSnn

Sasho Nikolov
fonte
ver também aplicações do grupo simétrico , a Wikipedia
vzn
todas respostas muito interessantes. vou ter dificuldade em escolher um para aceitar.
Sasho Nikolov 23/09/12
decente puramente teórico introdução / overview, Jovem Tableaux e as representações do grupo simétrico, por Zhao
vzn
2
Este artigo chegou ao quant-ph arXiv: uma solução para a tipicidade de duas partes usando a teoria da representação do grupo simétrico de Janis Noetzel.
Tyson Williams
A fatoração matricial baseada em simetria de Egner e Puschel usa elementos de e teoria da representação para uma fatoração / decomposição / multiplicação eficiente da matriz. veja S3.2 sobre simetria Perm-Perm. Sn
vzn

Respostas:

27

Aqui estão alguns outros exemplos.

  1. Diaconis e Shahshahani (1981) estudaram quantas transposições aleatórias são necessárias para gerar uma permutação quase uniforme. Eles provaram um limiar acentuado de 1/2 n log (n) +/- O (n). Gerando uma permutação aleatória com transposições aleatórias .

  2. Kassabov (2005) provou que é possível construir um expansor de grau limitado no grupo simétrico. Grupos simétricos e gráficos de expansão .

  3. Kuperberg, Lovett e Peled (2012) provaram que existem pequenos conjuntos de permutações que agem uniformemente nas k-tuplas. Existência probabilística de estruturas combinatórias rígidas .

Shachar Lovett
fonte
3
Obrigado Shachar, e bem-vindo ao cstheory! Tomei a liberdade para fixar os seus links: eles eram um pouco incompatíveis
Sasho Nikolov
14

Uma pergunta muito boa. Não sei a resposta completa e gostaria de saber ela mesma. No entanto, você pode achar o seguinte interessante. Se, em vez do grupo , considerarmos seu monóide 0-Hecke , ele uma representação em uma determinada classe de matrizes inteiras que atua por multiplicação tropical . Isso tem muitas aplicações interessantes em stringology, através de caminhos mais curtos de várias fontes em gráficos semelhantes a grades. Para detalhes, veja meu relatório técnico:SnH0(Sn)(min,+)

A. Tiskin. Comparação semi-local de strings: técnicas e aplicações algorítmicas. http://arxiv.org/abs/0707.3619

Alexander Tiskin
fonte
Obrigado! Parece muito interessante e com certeza vou dar uma olhada.
Sasho Nikolov 26/09/12
14

Aqui está um exemplo que eu sei:

`` Sobre a conjectura 'Log-Rank' na complexidade da comunicação '' , R.Raz, B. Spieker,

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

Eu acredito que há muito mais.

Klim
fonte
3
Você poderia resumir quais modelos de representação e como eles são aplicados?
Vijay D
@VijayD provavelmente Klim sabe mais, mas o problema aqui é como a complexidade da comunicação de uma função está relacionado ao logaritmo de sua classificação (pensando em como uma matriz real ). Eles constroem um de classificação e CC . O posto de é calculado por escrevê-lo como a soma de matrizes na representação regular def:{0,1}n×{0,1}n{0,1}f2d×2df2O(n)Ω(nloglogn)fSn
Sasho Nikolov
Na verdade, li este artigo há algum tempo, e agora não me lembro exatamente.
Klim
11

Aqui está um exemplo da computação quântica:

Roland, Jeremie; Roetteler, Martin; Magnin, Loïck; Ambainis, Andris (2011), "Adversaries Assistidos por Simetria para Geração de Estado Quântico", Anais da 26ª Conferência Anual da IEEE de 2011 sobre Complexidade Computacional, CCC '11, IEEE Computer Society, pp. 167-177, doi: 10.1109 / CCC. 2011.24

Eles mostram que a complexidade da consulta quântica de um determinado problema chamado Index Erasure é usando a teoria de representação do grupo simétrico para construir uma matriz adversa ideal para se conectar ao método do adversário quântico.Ω(n)

Robin Kothari
fonte
10
  1. O terceiro volume de Knuth da The Art of Computer Programming é dedicado à pesquisa e classificação e dedica muito à combinatória e permutações e à correspondência de Robinson-Schensted-Knuth , que é central na teoria das representações do grupo simétrico.

  2. Existem vários artigos de Ellis-Friedgut-Pilpel e Ellis-Friedgut-Filmus que resolvem problemas combinatórios extremos usando análise harmônica em . Não é bem o TCS, mas é bem próximo.Sn

  3. No início dos anos 90, Ajtai obteve resultados maravilhosos na representação modular de , motivada por questões de complexidade computacional. Não me lembro dos detalhes ou se foram publicados, mas vale a pena ler!Sn

Gil Kalai
fonte
Obrigado Gil! Acredito que um dos artigos de Ajtaj que você tem em mente é este: eccc.hpi-web.de/eccc-reports/1994/TR94-015/index.html . Acho que o aplicativo é para provar a complexidade do princípio do buraco de pombo, mas ainda não entendo a conexão.
Sasho Nikolov
6

O grupo simétrico desafia a forte amostragem de Fourier por Moore, Russell, Schulman

"mostramos que o problema do subgrupo oculto no grupo simétrico não pode ser resolvido com eficiência por uma forte amostragem de Fourier ... Esses resultados se aplicam ao caso especial relevante para o problema do isomorfismo de grafos."

com uma conexão para resolver o problema do isomorfismo gráfico através de abordagens de QM

sec 5 Teoria das representações do grupo simétrico

vzn
fonte
5

Mais estatística do que ciência da computação, mas ainda interessante: no capítulo 8 da monografia de Diaconis sobre representações geográficas de grupo em probabilidade e estatística , são desenvolvidas técnicas de análise espectral para dados associados a um grupoIsso estende a análise espectral mais clássica dos dados de séries temporais, onde o natural é o real ou o número inteiro a ser adicionado. Faz sentido considerar como quando os dados são fornecidos por classificações. A monografia é usada para interpretar os coeficientes de Fourier dos dados de classificação. Nesse caso, o conjunto de dados é representado porGGGSnf:SnR+ que mapeia as classificações (dadas por uma permutação) para a fração da população que prefere a classificação.

Também no mesmo capítulo, a análise de Fourier sobre os grupos simétricos e outros é usada para derivar modelos e testes ANOVA.

Uma extensão natural disso seria a teoria da aprendizagem estatística para classificar problemas que se beneficiam das técnicas teóricas da representação de maneira semelhante à maneira como a teoria da aprendizagem para classificação binária sob a distribuição uniforme se beneficiou da análise de Fourier no cubo booleano.

Sasho Nikolov
fonte
Qual é a estrutura natural do grupo para classificar problemas?
Suresh Venkat
1
@Suresh Eu tinha em mente o grupo simétrico, mas meu último parágrafo é mais positivo do que qualquer outra coisa. Eu tinha em mente um problema semelhante a junta nos rankings: aprender uma função que depende da ordem relativa de apenas alguns elementos de de poucas amostras. Talvez técnicas de Fourier pode dar limites amostra não triviaisf:Sn{0,1}[n]
Sasho Nikolov
5

A teoria da representação do grupo simétrico desempenha um papel fundamental na abordagem da Teoria da complexidade geométrica para limites mais baixos na multiplicação determinante ou na matriz.

Joshua Grochow
fonte
4
vzn
fonte
1
Eu sugiro fusão esta resposta com a outra referência permutações de aprendizagem
Sasho Nikolov
ok ... mesclando ...
vzn 25/09/12
-2

Neste artigo altamente citado por Beals, 1997, o STOC parece provar que o cálculo quântico de transformadas de Fourier sobre grupos simétricos está no BQP, isto é, tempo polinomial quântico

vzn
fonte
2
Novamente, isso acontece com o outro artigo quântico a que você se refere. a principal motivação para o desenvolvimento da transformação de Fourier não abeliana foi usá-la para resolver o problema do subgrupo oculto no grupo simétrico. o outro artigo que você cita mostra que essa abordagem não resolve o problema.
Sasho Nikolov 25/09/12
btw ser claro: o que quero dizer com o comentário acima é sugerir a se fundir esta resposta com a outra resposta QM e explicar como os dois estão relacionados (porque são)
Sasho Nikolov
ok Moore e outros citam Beals, embora não tenha sido assim que encontrei o artigo sobre Beals. pode mesclar mais tarde, mas agora algum público não parece como este Beals ref por qualquer motivo (antigo, substituído etc ...?)
vzn
não tenho certeza, acho que é uma referência aceitável. Um problema para mim é que você não explica por que é importante poder calcular a transformação de fourier não abeliana, como ela é motivada.
Sasho Nikolov
1
eu preferiria que as respostas fossem por si só e dessem ao leitor uma pista suficiente para poder decidir se deveria ler o artigo completo ou não. eu gostaria que a resposta mostrasse mais do que uma compreensão superficial do material.
Sasho Nikolov 25/09/12
-5

um exemplo mais antigo, mas ainda com pesquisas recentes / em andamento, parte dessa teoria aparece na matemática do "embaralhamento perfeito" , visto como um elemento do grupo simétrico e que era uma descoberta famosa na época. [1] menciona aplicações do algoritmo de processamento aleatório perfeito para paralelo e também a conexão com Cooley-Tukey O (n log n) DFT. [2] é mais recente. o shuffle perfeito aparece em processamento paralelo [3], design de memória e redes de classificação.

[1] Matemática do shuffle perfeito de Diaconis, Graham, Cantor. 1983

[2] Ciclos da permuta aleatória perfeita de várias vias por Ellis, Fan, Shallit (2002)

[3] Processamento paralelo com o embaralhamento perfeito de Stone, 1971

[4] Rede Omega baseada em embaralhamento perfeito

[5] Permutação no local paralela e seqüencial e embaralhamento perfeito usando involuções Yang et al (2012)

vzn
fonte
1
A teoria da representação é usada nesses trabalhos?
Sasho Nikolov 23/09/12
parece ser um caso especial disso
vzn 24/09/12
2
qual é um caso especial de quê? o shuffle perfeito é uma permutação. Estou perguntando, a teoria da representação é usada nas provas desses artigos? eu não encontrei nenhum.
Sasho Nikolov
3
caso contrário, existem modelos probabilísticos de embaralhamento (imperfeito) e o embaralhamento repetido usando um desses modelos é uma caminhada aleatória nas permutações. às vezes é possível analisar o tempo de mistura de uma caminhada aleatória usando análise de Fourier no grupo simétrico: Shachar deu um exemplo para o embaralhamento aleatório das transposições. suas referências são interessantes, mas não vejo nenhuma conexão com a teoria das representações: os trabalhos estão preocupados com alguns (dois em [1]) embaralhamentos determinísticos e os grupos de permutação que eles geram. a análise parece ser combinatória
Sasho Nikolov
o embaralhamento imperfeito também é interessante, mas todo o ponto da resposta é embaralhamento perfeito. parece que os mesmos resultados acima poderiam ser reformulados ou comprovados através da teoria da representação, ou estão usando alguns aspectos essenciais, sem referência óbvia / direta a ela. note shachars answer cita Diaconis, mesmo autor em um dos artigos desta resposta. em outras palavras, os autores acima certamente poderiam responder melhor à sua pergunta, mas minha expectativa é que eles respondessem pelo menos um pouco afirmativamente =) ... além de você ter descrito a teoria da representação como "maravilhosamente combinatória" em sua própria pergunta!
vzn