Parece que la teoría de la complejidad geométrica requiere mucho conocimiento de las matemáticas puras, como la geometría algebraica, la teoría de la representación.
Si bien soy estudiante de CS y NO tengo clases de matemáticas muy abstractas y puras, estoy interesado en este programa.
¿Existe una lista de "conocimiento mínimo" para aprender esta teoría?
Esta lista incluye notas de conferencias de CS o departamentos de matemáticas, encuestas de cualquier revista o conferencia, y libros de texto de matemática pura.
[ EDITAR: agregado más tarde ] Gracias por sus comentarios.
Teoría general de la informática: leí el libro de Sipser con el título "Introducción a la teoría de la informática"
Teoría de la complejidad: en particular, estoy interesado en modelos concretos para límites más bajos de complejidad. Así leí la parte de los "límites inferiores concretos" en el libro de texto de Arora-Barak. También tengo conocimientos básicos en varios capítulos del libro de complejidad de comunicación escrito por Nisan.
Matemáticas básicas: aprendí sobre álgebra lineal basada en pruebas, como la definición general del espacio vectorial, etc. y, sobre todo, el argumento de los cálculos basados en el argumento épsilon-delta.
Álgebra: He aprendido sobre la definición y ejemplos de grupo, anillo y campo. Tuve una clase para estudiantes de cs, y no he aprendido sobre la historia general de estos sistemas algebraicos.
fuente
Respuestas:
La respuesta corta : el conocimiento realmente mínimo de matemáticas para comprender la primera mitad del plan de GCT, una vez que haya visto un poco de grupos, anillos y campos, se expone básicamente en el Capítulo 3 de mi tesis. (autoenchufe desvergonzado ) Sin embargo, ese capítulo es incompleto, ya que no llego a la teoría de la representación como parte de las cosas. La teoría de la representación es crucial para la segunda mitad del plan (por eso estoy trabajando en extender ese capítulo para incluirlo).
Si realmente quiere entrar en GCT, Symmetry, Representations e Invariants de Goodman y Wallach y Actions and Invariants of Algebraic Groups de W. Ferrers Santos son relativamente independientes y tienen mucha buena información pertinente a GCT. No estoy seguro de si son las mejores fuentes para aprender, ya que solo aprendí sobre ellos después de haber aprendido mucho de este material, pero son buenos en términos de la proporción de lo que cubren a lo que es relevante para GCT. Fulton y Harris son excelentes para la teoría de la representación y muchos de los ejemplos / ejercicios en el libro son relevantes para GCT.
La respuesta más larga : realmente depende de qué / cuánto quieres aprender sobre GCT, como señaló Vijay. Los temas a continuación son justo lo que creo que son los antecedentes necesarios, ya que esa era la pregunta. No estoy seguro de que esta sea una lista completa; recomendaría intentar leer algunos de los documentos sobre GCT, y cuando se pierda, busque material de antecedentes. A medida que aprende el material de referencia, de vez en cuando vuelva a los documentos de GCT y vea si puede seguir más.
(Dependiendo de lo que quieras aprender, en realidad no estoy de acuerdo con Zeyu en que primero debas probar álgebra conmutativa graduada, aunque en algún momento aprender GCT será necesario).
Si desea comprender, por ejemplo, el reciente documento FOCS de Mulmuley , querrá comprender:
Si desea comprender el esquema general del enfoque GCT pero con algunos detalles matemáticos , le sugiero:
El problema permanente versus determinante. # P-completitud de permanente y GapL-completitud de determinante. Agrawal tiene una buena encuesta (solo un poco desactualizada) sobre esto, y las pruebas de integridad se pueden encontrar en el libro de Burgisser Completitud y reducción en la teoría de la complejidad algebraica .
Grupos y acciones grupales (los grupos algebraicos y las acciones grupales algebraicas son útiles, pero no necesarios en este nivel). Debes entender el teorema del estabilizador de órbita.
Afinar la geometría algebraica a través de Nullstellensatz de Hilbert. Básicamente, solo necesita comprender la correspondencia entre las variedades algebraicas afines y sus anillos de coordenadas.
Teoría básica de la representación deG Lnorte como en Fulton y Harris . Además de las definiciones básicas, debe conocer la reducibilidad completa de estas representaciones y el hecho de que las representaciones deG Lnorte se clasifican por particiones, pero no necesariamente necesita saber las pruebas / construcciones de este último.
Si desea comprender profundamente lo que está sucediendo (y no estoy seguro de poder afirmar que todavía estoy allí, pero creo que sé lo que necesito saber para llegar allí), probablemente también deba comprender:
La estructura de los grupos algebraicos reductivos y los cierres de órbitas en sus representaciones. Me gusta el libro de W. Ferrers Santos para esto, pero también Linear Algebraic Groups de Borel , The Classical Groups de Weyl y otros clásicos.
La maquinaria Luna-Vust (Teorema de corte de Luna, complejidad Luna-Vust)
Dualidad Tannakiana (ver el artículo de Deligne - Milne ; esta será una lectura difícil sin algunos antecedentes en teoría de categorías y grupos algebraicos afines). Esto esencialmente dice que "los grupos algebraicos (pro) afines están determinados por sus representaciones". No creo que necesite todo el trabajo, sino cómo recuperar un grupo de su categoría de representaciones (Cor. 3.4).
Más teoría de la representación , especialmente aplicada a los anillos de coordenadas de grupos algebraicos y sus cierres de órbita. Realmente me gusta el libro de Goodman y Wallach para esto, particularmente porque es básicamente autónomo y tiene mucho de lo que necesitas para entender GCT. (Además, muchas de las secciones expositivas / laterales y ejercicios en Fulton y Harris están en lo cierto para GCT, especialmente aquellos sobre los coeficientes de Littlewood-Richardson y Kronecker).
Si realmente quiere trabajar en la teoría de la representación , probablemente quiera comprender más teoría combinatoria / combinatoria algebraica. Realmente no conozco todas las referencias correctas para esto, pero ciertamente es imprescindible entender la regla de Littlewood-Richardson, y el libro de Fulton Young Tableaux es bueno para esto.
Los artículos más recientes sobre este lado de las cosas que conozco son Blasiak , Kumar y Bowman, De Visscher y Orellana .
Dependiendo de la dirección en la que desee ir, es posible que también desee examinar los grupos cuánticos, aunque esto no es necesariamente necesario (nota: estos no son un caso especial de grupos, sino más bien una generalización en una determinada dirección).
En el lado más geométrico de las cosas , querrá examinar cosas como la geometría diferencial para espacios tangentes y osculantes, curvatura, variedades duales y similares, que están subyacentes al límite inferior más conocido en perm vs. det debido a Mignon --Ressayre y seguido por Landsberg - Manivel - Ressayre . ( Mignon - Ressayre puede entenderse sin ninguna de estas cosas, pero puede ver su documento de forma flexible como el estudio de la curvatura de ciertas variedades; para una vista menos suelta, vea el uso de variedades duales en Landsberg - Manivel - Ressayre . ) (Ver también Cai, Chen y Li , que extiende Mignon - Ressayre a todas las características extrañas.) Ver también Landsberg y Kadish .
Si está interesado en el enfoque GCT para la multiplicación de matrices , se trata de rango de tensor, rango de borde y variedades secantes. Sugeriría mirar los documentos de Burgisser: Ikenmeyer , Landsberg y Ottaviani , Landsberg , la encuesta y el libro de Landsberg . Por supuesto, también sería bueno saber las cosas clásicas sobre la multiplicación de matrices (ambos límites superior e inferior), pero esa es una lata completamente separada de gusanos.
fuente