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 n. 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? n
fuente
Respuestas:
Aquí hay algunos otros ejemplos.
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 .
Kassabov (2005) demostró que se puede construir un expansor de grado acotado en el grupo simétrico. Grupos simétricos y gráficos expansores .
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 .
fuente
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:Sn H0(Sn) (min,+)
A. Tiskin. Comparación de cadenas semi-locales: técnicas y aplicaciones algorítmicas. http://arxiv.org/abs/0707.3619
fuente
Aquí hay un ejemplo que sé:
`` Sobre la conjetura 'Log-Rank' en la complejidad de la comunicación '' , R.Raz, B.Spieker,
Creo que hay mucho más.
fuente
Aquí hay un ejemplo de la computación cuántica:
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−−√)
fuente
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.
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
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
fuente
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
fuente
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 dispersaG G G Sn f:Sn→R+ 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.
fuente
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.
Bürgisser e Ikenmeyer prueban un límite inferior en el rango de frontera de la multiplicación de matrices usando la teoría de representación de .Sn
Para ver cómo la teoría de la representación de relaciona con los límites inferiores del determinante, consulte la Teoría de la complejidad geométrica II: Hacia obstrucciones explícitas para las incrustaciones entre variedades de clase y la Teoría de la complejidad geométrica VI: El cambio por positividadSn
fuente
Tesis doctoral de Huangs, RAZONAMIENTO PROBABILÍSTICO Y APRENDIZAJE SOBRE PERMUTACIONES: explotando las descomposiciones estructurales del grupo simétrico . la aplicación es "un escenario real de seguimiento de múltiples personas basado en cámara".
Inferencia probabilística teórica de Fourier sobre permutaciones de Huang, Guestrin, Guibas; Journal of Machine Learning Research 10 (2009) 997-1070. ver, por ejemplo, sec 5. Teoría de la representación en el grupo simétrico
otro documento de aplicación multipista. Seguimiento de objetos múltiples con representaciones del grupo simétrico (2007) por Kondor, Howard, Jebara
Distribución de probabilidad de aprendizaje sobre permutaciones por medio de coeficientes de Fourier, Irurozki, Calvo, Lozano (Dept CS / AI). ver sec 2 La transformada de Fourier en el grupo simétrico
fuente
Aplicación de la teoría de la representación de grupos simétricos para el cálculo de polinomios cromáticos de gráficos por Klin y Pech
fuente
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
fuente
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)
fuente