¿Aplicaciones de TCS a las matemáticas clásicas?

60

En TCS a menudo utilizamos resultados e ideas poderosas de las matemáticas clásicas (álgebra, topología, análisis, geometría, etc.).

¿Cuáles son algunos ejemplos de cuándo ha sido al revés?

Aquí hay algunos que conozco (y también para dar una idea del tipo de resultados que estoy preguntando):

  • Espumas cúbicas (Guy Kindler, Ryan O'Donnell, Anup Rao y Avi Wigderson: Cubos esféricos y redondeo en altas dimensiones, FOCS 2008)
  • El programa de teoría de la complejidad geométrica. (Aunque esto es técnicamente una aplicación de la geometría algebraica y la teoría de la representación a TCS, se les llevó a introducir nuevos grupos cuánticos y nuevas ideas puramente algebro-geométricas y de representación teórica en su búsqueda de P vs NP).
  • Trabaje en incrustaciones métricas inspiradas en algoritmos de aproximación y resultados de aproximación

En particular, no busco aplicaciones de TCS a la lógica (teoría de modelos finitos, teoría de prueba, etc.) a menos que sean particularmente sorprendentes: la relación entre TCS y la lógica es demasiado estrecha, estándar e histórica para los propósitos de esta pregunta.

Joshua Grochow
fuente
1
Esto es un poco complicado de responder. ¿La combinatoria queda fuera de las matemáticas clásicas?
arnab
2
La combinatoria es definitivamente la matemática clásica, pero creo que el mismo comentario se aplica a la combinatoria que a la lógica. Entonces: la conjetura de Kakeya de campo finito es un buen ejemplo, mientras que los nuevos diseños combinatorios motivados por los PRG están más cerca.
Joshua Grochow
Puede encontrar buenos ejemplos buscando resultados publicados en, digamos, Annals of Math por la comunidad de TCS.
MCH

Respuestas:

32

Los expansores se desarrollaron en gran medida en TCS y tienen profundas conexiones y aplicaciones con las matemáticas.

Gil Kalai
fuente
22

Hay una prueba de Dvir de la conjetura de Kakeya de campo finito.

Dai Le
fuente
3
Esto fue motivado por un problema en los extractores / fusiones (ver el artículo posterior de Zeev y Avi Wigderson). Otras mejoras (de Madhu Sudán, Shubhangi Saraf, Swastik Kopparty y Zeev Dvir) utilizaron más ideas de la informática teórica, específicamente de la decodificación de códigos de listas (el método de multiplicidades).
Dana Moshkovitz
1
Dos comentarios: el método algebraico utilizado por Dvir es uno de los métodos utilizados para resolver el problema clásico sobre distancias para conjuntos planos. terrytao.wordpress.com/2010/11/20/… y gilkalai.wordpress.com/2010/11/20/… .
Gil Kalai el
2
Segundo, los métodos de incidencia y los resultados de la geometría computacional y discreta tuvieron aplicaciones anteriores al problema (real) de Kakeya.
Gil Kalai el
20

Los principios de invariancia fueron motivados por la dureza de la aproximación, pero son teoremas analíticos útiles. El principio: una función de bajo grado, en la que cada una de las variables tiene una influencia pequeña, se comporta casi igual, sin importar si las entradas son variables aleatorias independientes o variables aleatorias gaussianas (correspondientes). Esta es una generalización del teorema del límite central; allí la función es el promedio de las variables.

Estabilidad acústica de funciones con bajas influencias: invariancia y optimismo E. Mossel, R. O'Donnell, K. Oleszkiewicz. Annals of Mathematics 171 (1), págs. 295-341 (2010). FOCS '05.

Los teoremas de prueba de bajo grado fueron motivados por aplicaciones PCP, pero son interesantes teoremas algebraicos. El principio: una función variable sobre un campo finito que, en promedio sobre las líneas en , está cerca en la distancia de Hamming a un polinomio de bajo grado en la línea , está cerca en la distancia de Hamming a un polinomio de bajo grado en toda la .F F n F nnFFnFn

La proximidad en la distancia de Hamming a un polinomio de bajo grado en un determinado espacio significa que la función se identifica con un polinomio de bajo grado en alguna fracción no despreciable del espacio.

Pruebas de bajo grado mejoradas y sus aplicaciones . S. Arora y M. Sudán. En ACM STOC 1997.

Una prueba de bajo grado de probabilidad de error subconstante y una caracterización de PCP de probabilidad de error subconstante de NP , R.Raz, S.Safra, Procedencia del 29º STOC, 1997, págs. 475-484

Dana Moshkovitz
fuente
19

Aunque soy parcial, creo que es justo decir que varias ideas de TCS han contribuido al progreso en la conjetura inversa de la norma de Gowers, véase, por ejemplo, el documento de Green y Tao .

Manu
fuente
77
Además, es justo decir que los componentes de la prueba del teorema de Szemeredi a través del lema de regularidad de hipergrafía (por Gowers, Tao, Rodl, Schacht y otros) fueron influenciados por el trabajo de Alon, Fischer, Shapira y otros en el desarrollo de versiones más fuertes del lema de regularidad del gráfico para probar la comprobabilidad de las propiedades del gráfico.
arnab
18

¿Es la teoría de la computabilidad parte de TCS? Si es así, la teoría de la computabilidad y la geometría diferencial de Bob Soare, que expone las aplicaciones de los resultados que obtuvo con Csima, es un ejemplo.

No sé por qué el enlace no aparece ... Aquí: http://www.people.cs.uchicago.edu/~soare/res/Geometry/geom.pdf

Aaron Sterling
fuente
2
Ya sea que cuente o no la computabilidad como parte de TCS, este es un ejemplo que me encanta que simplemente había olvidado mencionar. Es aún más genial porque se puede hacer usando la complejidad de Kolmogorov :).
Joshua Grochow
17

Extractores es otro lugar para buscar. Por ejemplo, el artículo de Barak-Kindler-Shaltiel-Sudakov-Wigderson'04 ofrece (entre otras cosas) mejores construcciones de gráficos de Ramsey (un problema que había estado abierto durante un tiempo en matemáticas discretas).

Moritz
fuente
15

De Wolf y Drucker mencionan en su encuesta sobre pruebas cuánticas acerca de la sorprendente conexión entre la complejidad de consulta cuántica y la aproximación de funciones simétricas por polinomios.ϵ

revs ilyaraz
fuente
13

La construcción del expansor Zig-Zag se usó para construir varios ejemplos interesantes de grupos con ciertas propiedades inesperadas, ver Meshulam-Wigderson , Rozenman-Shalev-Wigderson . La construcción en sí es muy interesante desde un punto de vista matemático puro, ya que utilizó herramientas completamente diferentes (motivadas por el punto de vista CS de tratar con la entropía) para construir expansores que las construcciones anteriores. (Sin embargo, tal vez la aplicación más famosa esté dentro del algoritmo de espacio de registro de TCS- Reingold para conectividad no dirigida ).

Boaz Barak
fuente
10

Permítanme mencionar un par de aplicaciones más:

Quizás la contribución más importante de TCS a las matemáticas puras es el arte de las reducciones. Las reducciones de la forma utilizada por TCS en la complejidad computacional y otros lugares representan un paradigma matemático / herramienta que está más desarrollado en TCS en comparación con otras áreas de las matemáticas.

La noción de una prueba probabilística: aquí no me refiero al método probabilístico (que tiene sus raíces en las matemáticas pero tiene muchas aplicaciones para CS), sino más bien al hecho de que una declaración matemática como la declaración que afirma un cierto número es primo, puede recibir una prueba "más allá de cualquier duda razonable". Es un avance conceptual proveniente de CS, aunque todavía no tenía muchas aplicaciones en la forma en que se practican las matemáticas.

Gil Kalai
fuente
1
No sabía que otras áreas de las matemáticas habían usado significativamente la idea de las reducciones. ¡Realmente agradecería cualquier referencia o puntero que pueda dar a tales trabajos! Además, tenía la impresión de que las pruebas probabilísticas surgieron de la combinatoria pura y no del TCS.
Joshua Grochow
3
Le expliqué lo que quiero decir con "prueba probabilística" en la versión editada de mi respuesta. Respecto a las reducciones: La complejidad computacional es un área de las matemáticas enraizada en la informática. Una característica de esta área es el uso de reducciones que juega un papel importante en el nivel conceptual y técnico. Está mucho más desarrollado que técnicas similares en otras áreas de las matemáticas. Por lo tanto, el arte de las reducciones dentro de TCS puede considerarse como una aplicación principal de TCS a las matemáticas. Creo que las reducciones de tipo CS también han influido en los matemáticos en otras áreas, y aún queda mucho por hacer.
Gil Kalai
Joshua, déjame darte una analogía. Supongamos que alguien se refiere al "cálculo" como una de las mayores aplicaciones de la física a las matemáticas clásicas. También se puede decir que el cálculo es principalmente importante para atacar problemas provenientes de la física que antes no eran "matemáticas clásicas". Aún así, creo que el cálculo es la principal contribución de la física a las matemáticas. Del mismo modo, las reducciones del tipo utilizado en la teoría de la complejidad es una contribución importante de TCS a las matemáticas. Describe un importante aparato matemático e ideas matemáticas que tienen un valor independiente (aunque no es tan importante como el cálculo)
Gil Kalai
G
1
@JoshuaGrochow no será difícil encontrar ejemplos no triviales de "caso general a reducciones especiales". Por ejemplo, la encuesta de Cassaza que vinculé en mi respuesta tiene toneladas de reducciones no triviales entre problemas equivalentes al problema de Kadison-Singer, algunos de ellos muy restringidos a primera vista. Tengo entendido que la geometría aritmética también está llena de tales cosas, es posible que sepa más. No estoy seguro de hasta qué punto TCS puede reclamar crédito por presentar este enfoque a problemas insolubles.
Sasho Nikolov
9

La prueba constructiva de Moser del Lema local de Lovasz utiliza ideas informáticas, ofrece una nueva prueba del lema local de Lovasz y resuelve un problema en el que la gente ha estado pensando durante bastante tiempo.

Peter Shor
fuente
9

El método de la función barrera de Batson-Spielman-Srivastava ha tenido varias aplicaciones a la geometría y al análisis funcional, surgió en la informática y es una forma muy original de argumento de función potencial, que recuerda el método de los estimadores pesimistas. Además, va en contra de la sabiduría convencional de que analizar el polinomio característico de las matrices aleatorias es intratable, y es mejor mirar los momentos de la matriz.

El método de la función de barrera se desarrolló por primera vez para demostrar la existencia de (y construir en tiempo polinomial determinista) esparcedores de gráficos que preservan sus propiedades espectrales. Dichos sparsifiers fueron motivados por aplicaciones algorítmicas: esencialmente cualquier algoritmo que necesite calcular cortes aproximadamente puede acelerarse al dar como entrada una versión espaciada de la entrada original.

1n

Avancemos rápidamente hasta 2013, y Marcus, Srivastava y Spielman utilizaron el método de función de barrera, con esteroides y aumentado con la maquinaria de los polinomios entrelazados , para resolver uno de los problemas más notorios en el análisis funcional, el problema de Kadison-Singer . Este problema surge de preguntas fundamentales en física matemática, pero va mucho más allá: se sabe que es equivalente a docenas de problemas en todas las matemáticas. Sin mencionar que muchos analistas (incluidos Kadison y Singer) ni siquiera pensaron que el problema tuviera una resolución positiva (la encuesta citada por Cassaza et al. Especula sobre posibles contraejemplos).

Sasho Nikolov
fuente
5

Un ejemplo que viene a la mente es el Teorema de inclusión de Higman y sus consecuencias teóricas grupales.

Teorema de inclusión de Higman: un grupo G se genera finitamente con una presentación recursiva si G es un subgrupo de un grupo presentado finitamente.

(Observe que la parte izquierda de la equivalencia tiene un componente computacional mientras que la derecha es puramente teórica de grupo).

Mike 2 revs
fuente
1
GHGWord(G)NPG
5

El significado de la aleatoriedad , lo que se considera una "secuencia aleatoria" y las preguntas relacionadas fueron importantes en matemáticas, teoría de la probabilidad y estadística durante siglos. La informática teórica (y la teoría de la complejidad) ofrece ideas profundas y convincentes muy sólidas para la comprensión de la aleatoriedad.

Mientras que el método probabilístico comenzó en la desradiación matemática, que es un concepto matemático importante, se desarrolla principalmente en CS.

Esto está relacionado con la respuesta de Moritz .

Gil Kalai
fuente
5

Teoría de autómatas y algebraicidad

La teoría de los autómatas ha dado algunos resultados interesantes para caracterizar la algebraicidad. Menciono dos de ellos, con referencias. De ninguna manera es exhaustivo.

Fq(t)

Fq(t)qq=pspsFq[[t]]Fq

Fq(t)Fq(t)

i=0aitiFq(t){ai}i=0p

Fq(t)

iIxiti,
IQFq(t)

iIaitiFq(t){ai}iIp

2. Números trascendentales

Las secuencias automáticas también se utilizan para caracterizar números trascendentales. Por ejemplo,

b2xRx={xi}i=0b

  1. xx
  2. xbx
  3. x

¡Por supuesto, el primer artículo es un resultado muy clásico!

Referencias

[1] Gilles Christol. Conjuntos presque périodiques k-reconnaissables . En Theoretical Computer Science 9 (1), pp 141-145, 1979.

[2] Kiran S. Kedlaya. Autómatas finitos y extensiones algebraicas de campos de funciones . En Journal de théorie des nombres de Bordeaux 18 , pp 379-420, 2006. arXiv: math / 0410375 .

[3] Boris Adamcweski, Yann Bugeaud. Sobre la complejidad de los números algebraicos I. Expansiones en bases enteras . En Annals of Mathematics 165 (2), pp 547-565, 2007.

Bruno
fuente
El teorema (Adamczewski y Bugeaud [3]) puede estar equivocado o ser mal entendido
XL _At_Here_There
4

Lτ

L

τpτ(1+τ)cc

Bruno
fuente
1

En mi humilde opinión, TCS es una rama de las matemáticas y lo pondría un poco más amplio. Vivimos en la era algorítmica, casi todos, en todas las actividades humanas, inventamos / reinventamos algoritmos, principalmente heurística. Pero algunos de esos algoritmos son 1. buenos; 2. contener (enterrado) respuestas a preguntas matemáticas profundas; 3. Espere un análisis matemático profesional / mejora / atención. Mi experiencia personal: un poder sorprendente de una heurística de aprendizaje de física / máquina, es decir, la aproximación Bethe, como técnica de prueba. El principal problema es que los posibles encuentros de este tipo ocurren principalmente en la industria, donde a nadie le importan esas ideas / revelaciones no relacionadas con el producto.

gurvits leonidos
fuente