Aplicaciones de la teoría de la representación del grupo simétrico.

42

Inspirado por esta pregunta y en particular el párrafo final de la respuesta de Or, tengo la siguiente pregunta:

¿Conoces alguna aplicación de la teoría de la representación del grupo simétrico en TCS?

El grupo simétrico es el grupo de todas las permutaciones de con composición de operación de grupo. Una representación de es un homomorfismo de al grupo lineal general de matrices complejas invertibles . Una representación actúa en mediante la multiplicación de matrices. Una representación irreducible de es una acción que no deja un subespacio adecuado de invariante. Las representaciones irreducibles de grupos finitos permiten definir una transformación de Fourier sobre grupos no abelianos. { 1 , , n } S n S n n × n C n S n C nSn{1,,n}SnSnn×nCnSnCn. Esta transformada de Fourier comparte algunas de las bonitas propiedades de la transformada discreta de Fourier sobre grupos cíclicos / abelianos. Por ejemplo, la convolución se convierte en multiplicación puntual en la base de Fourier.

La teoría de la representación del grupo simétrico es bellamente combinatoria. Cada representación irreducible de corresponde a una partición entera de . ¿Esta estructura y / o la transformación de Fourier sobre el grupo simétrico ha encontrado alguna aplicación en TCS? nSnn

Sasho Nikolov
fuente
ver también aplicaciones del grupo simétrico , wikipedia
vzn
Todas las respuestas muy interesantes. Voy a tener dificultades para elegir uno para aceptar.
Sasho Nikolov
Introducción / resumen decente puramente teórico, Young Tableaux and the Representations of the Symmetric Group, por Zhao
vzn
2
Este artículo acaba de alcanzar el arXiv cuantitativo: una solución a la tipicidad de dos partes utilizando la teoría de representación del grupo simétrico de Janis Noetzel.
Tyson Williams
La factorización de matriz basada en simetría de Egner y Puschel utiliza elementos de y la teoría de representación para la factorización / descomposición / multiplicación de matriz eficiente. ver S3.2 sobre simetría Perm-Perm. Sn
vzn

Respuestas:

27

Aquí hay algunos otros ejemplos.

  1. Diaconis y Shahshahani (1981) estudiaron cuántas transposiciones aleatorias se requieren para generar una permutación casi uniforme. Probaron un umbral agudo de 1/2 n log (n) +/- O (n). Generando una permutación aleatoria con transposiciones aleatorias .

  2. Kassabov (2005) demostró que se puede construir un expansor de grado acotado en el grupo simétrico. Grupos simétricos y gráficos expansores .

  3. Kuperberg, Lovett y Peled (2012) demostraron que existen pequeños conjuntos de permutaciones que actúan de manera uniforme en las k-tuplas. Existencia probabilística de estructuras combinatorias rígidas .

Shachar Lovett
fuente
3
Gracias Shachar, y bienvenido a cstheory! Me tomé la libertad de arreglar sus enlaces: estaban un poco desajustados
Sasho Nikolov
14

Una muy buena pregunta. No sé la respuesta completa y me gustaría saberlo yo mismo. Sin embargo, puede encontrar lo siguiente interesante. Si, en lugar del grupo , consideramos su monoide 0-Hecke , tiene una representación en una cierta clase de matrices enteras que actúa por multiplicación tropical . Esto tiene muchas aplicaciones interesantes en stringología, a través de rutas más cortas de múltiples fuentes en gráficos de cuadrícula. Para más detalles, vea mi informe técnico:SnH0(Sn)(min,+)

A. Tiskin. Comparación de cadenas semi-locales: técnicas y aplicaciones algorítmicas. http://arxiv.org/abs/0707.3619

Alexander Tiskin
fuente
¡Gracias! Esto se ve muy interesante y definitivamente lo comprobaré.
Sasho Nikolov
14

Aquí hay un ejemplo que sé:

`` Sobre la conjetura 'Log-Rank' en la complejidad de la comunicación '' , R.Raz, B.Spieker,

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

Creo que hay mucho más.

Klim
fuente
3
¿Podría resumir cuáles son los modelos de representación y cómo se aplica?
Vijay D
@VijayD probablemente Klim sabe más, pero el problema aquí es cómo la complejidad de comunicación de una función está relacionado con el registro de su rango (pensando en como una matriz real ). Construyen una de rango y CC . El rango de se calcula al escribirlo como la suma de las matrices en la representación regular def:{0,1}n×{0,1}n{0,1}f2d×2df2O(n)Ω(nloglogn)fSn
Sasho Nikolov el
En realidad, leí este artículo hace algún tiempo, así que ahora no lo recuerdo exactamente.
Klim
11

Aquí hay un ejemplo de la computación cuántica:

Roland, Jeremie; Roetteler, Martin; Magnin, Loïck; Ambainis, Andris (2011), "Adversarios asistidos por simetría para la generación de estado cuántico", Actas de la 26a Conferencia Anual de IEEE 2011 sobre Complejidad Computacional, CCC '11, IEEE Computer Society, pp. 167-177, doi: 10.1109 / CCC. 2011.24

Muestran que la complejidad de la consulta cuántica de un cierto problema llamado Index Erasure es usando la teoría de representación del grupo simétrico para construir una matriz adversaria óptima para conectarse al método adversario cuántico.Ω(n)

Robin Kothari
fuente
10
  1. El tercer volumen de Knuth de The Art of Computer Programming se dedica a buscar y clasificar, y dedica mucho a la combinatoria y las permutaciones y a la correspondencia Robinson-Schensted-Knuth , que es central en la teoría de la representación del grupo simétrico.

  2. Hay varios documentos de Ellis-Friedgut-Pilpel y Ellis-Friedgut-Filmus que resuelven problemas combinatorios extremos utilizando análisis armónicos en . No del todo TCS, pero bastante cerca.Sn

  3. Ajtai tuvo a principios de los 90 resultados maravillosos en la representación modular de que fueron motivados por preguntas de complejidad computacional. No recuerdo los detalles o si fue publicado, ¡pero vale la pena leerlo!Sn

Gil Kalai
fuente
Gracias gil! Creo que uno de los documentos de Ajtaj que tienes en mente es este: eccc.hpi-web.de/eccc-reports/1994/TR94-015/index.html . Creo que la aplicación es una prueba de la complejidad del principio del casillero, pero todavía no entiendo la conexión.
Sasho Nikolov
6

El grupo simétrico desafía el muestreo fuerte de Fourier por Moore, Russell, Schulman

"demostramos que el problema oculto del subgrupo sobre el grupo simétrico no puede resolverse eficientemente mediante un fuerte muestreo de Fourier ... Estos resultados se aplican al caso especial relevante para el problema del isomorfismo gráfico".

con una conexión para resolver el problema del isomorfismo gráfico a través de enfoques QM

sec 5 Teoría de la representación del grupo simétrico

vzn
fuente
5

Más estadísticas que la informática, pero sigue siendo interesante: En el capítulo 8 en la monografía Diaconis' en Grupo Gepresentations en probabilidad y estadística , técnicas de análisis espectral de los datos asociados a un grupo se desarrollan. Esto amplía el análisis espectral más clásico de datos de series de tiempo, donde el natural son los reales o los enteros que se suman. Tiene sentido tomar para ser cuando los datos son dados por clasificaciones. La monografía entra en la interpretación de los coeficientes de Fourier de los datos de clasificación. En ese caso, el conjunto de datos está representado por una dispersaGGGSnf:SnR+ que asigna clasificaciones (dadas por una permutación) a la fracción de la población que prefiere la clasificación.

También en el mismo capítulo, el análisis de Fourier sobre los grupos simétricos y otros se utiliza para derivar modelos y pruebas ANOVA.

Una extensión natural de esto sería la teoría del aprendizaje estadístico para clasificar los problemas que se beneficia de las técnicas teóricas de representación de una manera similar a la forma en que la teoría del aprendizaje para la clasificación binaria bajo la distribución uniforme se ha beneficiado del análisis de Fourier en el cubo booleano.

Sasho Nikolov
fuente
Sin embargo, ¿cuál es la estructura de grupo natural para los problemas de clasificación?
Suresh Venkat
1
@Suresh Tenía en mente el grupo simétrico, pero mi último párrafo es más ilusorio que cualquier otra cosa. Tenía en mente un problema similar a una junta en las clasificaciones: aprender una función que depende del orden relativo de solo unos pocos elementos de partir de pocas muestras. Tal vez las técnicas de Fourier pueden dar límites de muestra no trivialesf:Sn{0,1}[n]
Sasho Nikolov
5

La teoría de la representación del grupo simétrico juega un papel clave en el enfoque de la Teoría de la Complejidad Geométrica para los límites inferiores en el determinante o en la multiplicación de matrices.

Joshua Grochow
fuente
4
vzn
fuente
1
Sugeriría fusionar esta respuesta con la otra referencia de permutaciones de aprendizaje
Sasho Nikolov el
ok ... fusionando ...
vzn
-2

En este artículo altamente citado de Beals, 1997, STOC parece demostrar que el cálculo cuántico de las transformadas de Fourier sobre grupos simétricos está en BQP, es decir, el tiempo polinómico cuántico

vzn
fuente
2
de nuevo, esto va con el otro papel cuántico al que se refiere. La principal motivación para desarrollar la transformada de Fourier no abeliana era usarla para resolver el problema de subgrupos ocultos sobre el grupo simétrico. el otro documento que cita muestra que este enfoque no resuelve el problema.
Sasho Nikolov
para ser claros: lo que quiero decir con el comentario anterior es sugerir fusionar esta respuesta con la otra respuesta de QM y explicar cómo se relacionan los dos (porque lo están)
Sasho Nikolov
ok Moore et al citan Beals, aunque no es así como encontré el artículo de Beals. podría fusionarse más tarde, pero en este momento a algún público no parece gustarle esta referencia de Beals por cualquier razón (¿antigua, reemplazada, etc.?)
vzn
No estoy seguro, creo que es una referencia aceptable. Un problema para mí es que no explican por qué es importante poder calcular la transformación de Fourier no abeliana, cómo está motivada.
Sasho Nikolov
1
preferiría que las respuestas sean independientes y le den al lector una pista suficiente para poder decidir si leer el artículo completo o no. Me gustaría que la respuesta muestre más que una comprensión superficial del material.
Sasho Nikolov
-5

Un ejemplo más antiguo, pero aún con investigaciones recientes / en curso, parte de esta teoría aparece en las matemáticas de la "combinación perfecta" , vista como un elemento del grupo simétrico y que fue un descubrimiento famoso en ese momento. [1] menciona aplicaciones de la combinación perfecta de algoritmos de procesamiento en paralelo y también la conexión a Cooley-Tukey O (n log n) DFT. [2] es más reciente. la combinación aleatoria perfecta aparece en el procesamiento paralelo [3], el diseño de la memoria y las redes de clasificación.

[1] Matemáticas de la combinación perfecta por Diaconis, Graham, Cantor. 1983

[2] Ciclos de la permutación aleatoria perfecta de múltiples vías por Ellis, Fan, Shallit (2002)

[3] Procesamiento en paralelo con la combinación perfecta de Stone, 1971

[4] Red Omega basada en una combinación perfecta

[5] Permutación en el lugar paralela y secuencial y barajadura perfecta usando involuciones Yang et al (2012)

vzn
fuente
1
¿Se utiliza la teoría de la representación en estos documentos?
Sasho Nikolov
parece ser un caso especial
vzn
2
¿Cuál es un caso especial de qué? La combinación perfecta es una permutación. Estoy preguntando, ¿se utiliza la teoría de la representación en las pruebas de estos documentos? No encontré ninguno.
Sasho Nikolov
3
de lo contrario, existen modelos probabilísticos de barajadura (imperfecta), y la barajadura repetida usando uno de estos modelos es una caminata aleatoria sobre permutaciones. a veces se puede analizar el tiempo de mezcla de una caminata aleatoria de este tipo utilizando un análisis de Fourier en el grupo simétrico: Shachar dio un ejemplo para la combinación aleatoria de transposiciones. Sus referencias son interesantes, pero no veo ninguna conexión con la teoría de la representación: los documentos se refieren a unos pocos (dos en [1]) barajas deterministas y los grupos de permutación que generan. el análisis parece ser combinatorio
Sasho Nikolov
La combinación imperfecta también es interesante, pero el punto completo de la respuesta es la combinación perfecta. Parece que los mismos resultados anteriores podrían ser refundidos, o probados a través de la teoría de la representación, o están utilizando algunos aspectos centrales sin referencia obvia / directa. note shachars answer cita a Diaconis, el mismo autor en uno de los artículos de esta respuesta. en otras palabras, los autores anteriores seguramente podrían responder mejor a su pregunta, pero mi expectativa es que responderían al menos de manera afirmativa =) ... ¡además de que acaba de describir la teoría de la representación como "bellamente combinatoria" en su propia pregunta!
vzn