Impacto del programa de Grothendieck en TCS

27

Grothendieck ha fallecido . Tuvo un impacto masivo en las matemáticas del siglo XX que continuaron hasta el siglo XXI. Esta pregunta se hace algo en el estilo / espíritu, por ejemplo, de las Contribuciones de Alan Turing a la informática .

¿Cuáles son las principales influencias de Grothendieck en la informática teórica?

vzn
fuente
obituario en inglés / ABCNews
vzn
Quizás esto es relevante: ¿Grothendieck es una computadora?
babou
66
Espero que alguien de la teoría B escriba sobre teoría de categorías y topologías de Grothendieck (¿o su trabajo allí no es relevante para la informática?).
Sasho Nikolov
1
fyi algún bosquejo / esquema de una respuesta de reddit / "frobenius"
vzn
2
Quizás @AndrejBauer pueda ayudar.
Sasho Nikolov

Respuestas:

28

La desigualdad de Grothendieck , desde sus días en el análisis funcional, se demostró inicialmente que relaciona normas fundamentales sobre espacios de productos tensoriales. Grothendieck llamó a la desigualdad "el teorema fundamental de la teoría métrica de los espacios de productos tensoriales", y la publicó en un periódico ahora famoso en 1958, en francés, en una revista brasileña de circulación limitada. El documento fue ignorado en gran medida durante 15 años, hasta que Lindenstrauss y Pelczynski lo redescubrieron (después de que Grothendieck había dejado el análisis funcional). Dieron muchas reformulaciones de los principales resultados del documento, lo relacionaron con investigaciones sobre operadores absolutamente sumarios y normas de factorización, y observaron que Grothendieck había resuelto problemas "abiertos" que surgieron después deEl artículo fue publicado. Pisier da una descripción muy detallada de la desigualdad, sus variantes y su tremenda influencia en el análisis funcional en su encuesta .

max { Σ i , j un i ju i , v j : u 1 , ... , u m , v 1 , , v nS

max{xTAy:x{1,1}m,y{1,1}n}
S n + m - 1 R n + m
max{i,jaijui,vj:u1,,um,v1,,vnSn+m1},
Sn+m1Rn+m. Las pruebas de la desigualdad dan "algoritmos de redondeo", y de hecho el redondeo aleatorio de hiperplanes de Goemans-Williamson hace el trabajo (pero da una constante subóptima). Sin embargo, la desigualdad de Grothendieck es interesante porque el análisis del algoritmo de redondeo debe ser "global", es decir, analizar todos los términos de la función objetivo juntos.

Dicho esto, no debería sorprendernos que la desigualdad de Grothendiecks haya encontrado una segunda (¿tercera? ¿Cuarta?) Vida en informática. Khot Naor encuesta de sus múltiples aplicaciones y conexiones de optimización combinatoria.

La historia no termina ahí. La desigualdad está relacionada con las violaciones de la desigualdad de Bell en la mecánica cuántica (ver el artículo de Pisier), fue utilizada por Linial y Shraibman en el trabajo sobre la complejidad de la comunicación, e incluso resultó útil en el trabajo sobre el análisis de datos privados (conector descarado).

Sasho Nikolov
fuente
1
Aquí hay otro texto sobre la desigualdad de Grothendieck y CS. Pero no estoy calificado para comentar.
babou
Una conferencia de Giles Pisier en IHES también podría ser interesante: dailymotion.com/video/… (desafortunadamente es interrumpida por anuncios molestos).
Sasho Nikolov
17

El impacto de Grothendieck se puede sentir en la teoría de los tipos y la lógica. Por ejemplo, el volumen de más de 700 páginas de Bart Jacobs, la lógica categórica y la teoría de tipos, ofrece un tratamiento uniforme de varias teorías de tipos ( teoría del tipo , donde ) basado en la noción categórica de las fibraciones de Grothendieck (también llamadas fibraciones cartesianas). Del mismo modo, la noción de Topos , también debido a Grothendieck, desempeña un papel importante en proporcionar semántica categórica a las lógicas y teorías de tipos, lo cual es de interés tanto para los lógicos como para los científicos teóricos de la computación.X { simple , dependiente , polimórfico , de orden superior }XX{simple, dependent, polymorphic, higher-order}

Dave Clarke
fuente
1
@NikolajK No hay un significado formal real para mi uso de over - El Capítulo 11 del libro aborda la teoría del tipo dependiente de orden superior, por ejemplo.
Dave Clarke
12

pags

Supongo que la visión de Mulmuley de generalización de la hipótesis de Riemann sobre campos finitos provenientes de las conjeturas de Weil puede considerarse como una pregunta que originalmente tuvo resultados fructíferos de la cohomología etale de Grothendieck.

T ....
fuente
1
¿Son estas aplicaciones en informática teórica? Todo me parece matemático, o probablemente ese otro poco de TCS.
Dave Clarke
77
VnortePAGSVPAGS