¿Ejemplos de matemáticas "no relacionadas" que juegan un papel fundamental en TCS?

74

Enumere ejemplos en los que se utilizó por primera vez un teorema de las matemáticas que normalmente no se consideraba aplicable en informática para probar un resultado en informática. Los mejores ejemplos son aquellos en los que la conexión no era obvia, pero una vez que se descubrió, es claramente la "forma correcta" de hacerlo.

Esta es la dirección opuesta de la pregunta ¿ Aplicaciones de TCS a las matemáticas clásicas?

Por ejemplo, vea "Teorema y aislamiento de Green en gráficos planos" , donde se vuelve a demostrar un teorema de aislamiento (que ya se conocía utilizando una prueba técnica) utilizando el Teorema de Green a partir del cálculo multivariado.

¿Qué otros ejemplos hay?

Derrick Stolee
fuente
Wiki de la comunidad.
Dave Clarke el
Wiki de la comunidad ahora está en su lugar.
Derrick Stolee
Sorprendente cuántos ejemplos hay sobre topología y geometría. ¿Estamos más sorprendidos por estos dos temas?
Suresh Venkat
77
Una vez que se dan suficientes ejemplos del Área X, ¿hace que el Área X ya no esté "sin relación"?
András Salamon

Respuestas:

38

Maurice Herlihy, Michael Saks, Nir Shavit y Fotios Zaharoglou obtuvieron el premio Godel en 2004 por su uso de la topología algebraica en el estudio de algunos problemas en la informática distribuida.

Warren Schudy
fuente
1
¡Este es un gran ejemplo!
Ryan Williams el
25

Tengo un ejemplo de un trabajo que escribí junto con Noga Alon y Muli Safra hace unos años:

Noga usó teoremas de punto fijo de topología algebraica para probar el "Teorema de división de collar": si tiene un collar con cuentas de tipos t y desea dividir partes de él entre b personas para que cada uno obtenga el mismo número de cuentas de cada tipo ( suponga que b divide t), siempre puede hacerlo cortando el collar como máximo (b-1) t lugares.

Usamos este teorema para construir un objeto combinatorio que usamos para probar la dureza de la aproximación de Set-Cover.

Aquí hay más información: http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest.html

Dana Moshkovitz
fuente
25

En retrospectiva, esto puede ser obvio, pero siempre me ha gustado la aplicación de Steele, Yao y Ben-Or del teorema Oleinik-Petrovsky / Milnor / Thom (que limita los números Betti de conjuntos semi-algebraicos reales) para demostrar que es más bajo límites en el árbol de decisión algebraico y los modelos de cálculo de árbol de computación algebraico.

Jeffε
fuente
1
El tipo de resultados "en retrospectiva, es obvio" es el mejor tipo de aplicaciones. La retrospectiva es 20/20.
Derrick Stolee
25

Uno de mis resultados favoritos es el uso de argumentos topológicos en la prueba de Lovasz de la conjetura de Kneser , y el uso de métodos topológicos ( y de teoría de grupos ) en el ataque de Kahn-Saks-Sturtevant contra la fuerte conjetura de Aandera-Rosenberg-Karp sobre la evasión .

Suresh Venkat
fuente
+1. El uso de argumentos topológicos para probar declaraciones combinatorias es verdaderamente épico. Los lectores interesados ​​pueden encontrar más información aquí: en.wikipedia.org/wiki/Topological_combinatorics
Robin Kothari
1
@Robin: ¿O qué tal argumentos geométricos? El teorema principal del clásico artículo de Bayer-Diaconis sobre la mezcla de cola de milano se descubrió al pensar en la barajadura como una transformación para preservar el volumen (el mapa del panadero: doblar y doblar (mod 1) a lo largo de cada eje) del cubo 52. Desafortunadamente, eliminaron la mayoría de los rastros de la intuición geométrica del artículo final al reemplazarlo con una combinatoria discreta.
Según Vognsen el
@Per Vognsen: No estoy familiarizado con ese trabajo, así que gracias por el puntero. Lo echaré un vistazo.
Robin Kothari
2
Es posible que desee agregar " métodos topológicos y de teoría de grupos " para Kahn-Saks-Sturtevant. Después de todo, utilizan de manera crucial acciones grupales en complejos simpliciales.
Joshua Grochow
2
Me preguntaba si vale la pena "despertar" este hilo después de un año para señalar una referencia ... pero entonces es un gran hilo, así que ¿por qué no? El resultado de Lovasz y otros resultados, así como una introducción a la "topología algebraica para combinatorios" se pueden encontrar en la monografía de Matousek
Sasho Nikolov
22

La teoría de representación de grupos finitos se utiliza en el enfoque de Cohn-Kleinberg-Szegedy-Umans para la multiplicación de matrices . Muestran que si existen familias de productos de coronas de abelian con grupos simétricos que satisfacen ciertas condiciones, entonces existen algoritmos de multiplicación matricial de complejidad cuadrática.

La teoría de la representación (de grupos algebraicos) también aparece en el enfoque de la teoría de la complejidad geométrica de Mulmuley y Sohoni hacia los límites inferiores. Aún no está claro si esto cuenta como una aplicación, ya que aún no se han probado nuevos resultados de complejidad con este enfoque, pero al menos se ha hecho una conexión interesante entre dos áreas que a primera vista parecen totalmente ajenas.

Joshua Grochow
fuente
21

Hay muchos ejemplos de este tipo. Cuando aprendí por primera vez la teoría de la complejidad, me pareció sorprendente que los teoremas básicos sobre las raíces de polinomios (como el Lema Schwartz-Zippel-DeMillo-Lipton) tuvieran algo que ver con la cuestión de si las pruebas interactivas pueden simular el espacio polinómico ( ) Por supuesto, esas propiedades de los polinomios ya se habían utilizado en trabajos anteriores, y hoy en día el uso de cálculos "polinomiales" se ha vuelto bastante estándar en la teoría de la complejidad.IP=PSPACE

Ryan Williams
fuente
77
También disfruto el truco polinómico para encontrar coincidencias perfectas en gráficos bipartitos mediante el muestreo aleatorio del determinante (gracias, Lovász).
Derrick Stolee
21

La teoría de la aproximación (que trata de aproximar funciones de valor real posiblemente complicadas o no naturales mediante funciones simples, como polinomios de bajo grado) ha tenido muchos usos en la complejidad del circuito, la complejidad de la consulta cuántica, la pseudoaleatoriedad, etc.

Creo que una de las mejores aplicaciones de herramientas de esta área proviene de este artículo de Beigel, Reingold y Spielman, donde demostraron que la clase de complejidad PP está cerrada en la intersección utilizando el hecho de que la función de signo puede aproximarse por un valor bajo. -graduar la función racional.

Nisan y Szegedy y Paturi mostraron límites inferiores para aproximar funciones simétricas por polinomios de bajo grado. Este método se usa con frecuencia para probar los límites inferiores de la complejidad de la consulta cuántica. Ver las notas de clase de Scott Aaronson , por ejemplo.

Srikanth
fuente
20

Otra idea hermosa: la idea de Yao de usar principios minimax y la prueba de que los juegos mixtos tienen un equilibrio (esencialmente dualidad de programación lineal) para mostrar límites inferiores en algoritmos aleatorios (al construir una distribución sobre las entradas a un algoritmo determinista).

Suresh Venkat
fuente
77
También la prueba de Noam Nisan al Hard Core Lemma de Russell Impagliazzo (en el artículo original de Russell)
Dana Moshkovitz
17

Los teoremas de puntos fijos están por todas partes ...

Pero un ejemplo bastante sorprendente de geometría emergente de la nada es el resultado de comparación efectivo. Aquí, dado un orden parcial definido sobre un conjunto de elementos, considere el conjunto de permutaciones de los objetos que son compatibles con el orden parcial dado. La pregunta es elegir la comparación más efectiva para hacer a continuación; es decir, cuál es la comparación que reduciría el número de permutaciones compatibles con el nuevo orden parcial (por supuesto, hay dos posibles órdenes parciales, dependiendo del resultado de esta comparación única). Se sabe que siempre hay una comparación que reduce el número de permutaciones por un factor constante (por lo tanto, puede ordenar enO ( log n ! )nO(logn!)comparaciones, duh). La prueba de este hecho pasa por la geometría de los politopos de alta dimensión. Específicamente, la prueba utiliza la desigualdad de Brunn-Minkowski. Una buena presentación de esto se encuentra en el libro de Matousek sobre Conferencias sobre geometría discreta (Sección 12.3). La prueba original es de Kahn y Linial, desde aquí .

Sariel Har-Peled
fuente
15

Hay muchos usos de la teoría de la información en la informática teórica: por ejemplo, para probar los límites inferiores de los códigos decodificables localmente (ver Katz y Trevisan), en la prueba de Raz del teorema de la repetición paralela, en la complejidad de la comunicación (ver, por ejemplo, el hilo de trabajo sobre la compresión de la comunicación, por ejemplo, el trabajo relativamente reciente de Barak, Braverman, Chen y Rao, y las referencias allí), y mucho más trabajo.

Dana Moshkovitz
fuente
¿Pero estos usos son realmente "no relacionados"? Al menos desde un punto de vista ingenuo, me parece que la teoría de la información es una de las primeras áreas que viene a la mente cuando uno escucha por primera vez la definición de, por ejemplo, códigos decodificables localmente.
arnab
Estoy de acuerdo en que la teoría de la información está relacionada con códigos, por ejemplo, y los códigos están relacionados con TCS. La repetición paralela es quizás un ejemplo más contundente: ¿por qué pensaría en usarlo para la amplificación de sonido para PCP?
Dana Moshkovitz
Sí, estoy completamente de acuerdo en que la repetición paralela es un ejemplo sorprendente.
arnab
14

Alon y Naor utilizaron la desigualdad de Grothendieck para probar un algoritmo de aproximación en el problema de corte máximo . Creo que hay trabajos posteriores sobre ese tema, pero no soy un experto.

Curiosamente, Cleve, Hoyer, Toner y Watrous usaron el mismo teorema para analizar los juegos cuánticos XOR, y Linial y Shraibman lo usaron para la complejidad de la comunicación cuántica. Hasta donde yo sé, Tsirelson descubrió la relación entre la desigualdad de Grothendieck y los fundamentos de la física cuántica en 85, pero los dos resultados que mencioné se refieren específicamente a la informática.

Bagazo
fuente
Uhm, esto no es exacto. Alon y Naor aproximaron la norma de corte de una matriz; esto está relacionado con el corte máximo pero no es lo mismo.
Sasho Nikolov
13

Un buen ejemplo es el teorema de Barrington:

Si una función booleana es computable por un circuito de profundidad , entonces es computable por un programa de ramificación de ancho 5 y longitud .d f 4 dfdf4d

La prueba usa el grupo (porque tiene dos elementos que se conjugan entre sí y con su conmutador), pero se puede generalizar para trabajar en cualquier grupo no solucionable.S5

Diego de Estrada
fuente
12

Plug desvergonzado: uso de la conjetura isotrópica (y la geometría convexa en general) en el diseño de mecanismos diferencialmente privados aproximadamente óptimos para consultas lineales en mi trabajo con Moritz Hardt .

Para responder parcialmente a la pregunta anterior de Suresh, creo que la pregunta original es un poco complicada debido a que "normalmente no se considera que se aplique en informática". Algunas de estas técnicas que pueden parecer originalmente "no relacionadas" se vuelven "normales" con el tiempo. Entonces, la más exitosa de estas técnicas (por ejemplo, análisis de Fourier en Kahn-Kalai-Linial, incrustaciones métricas en Linial-London-Rabinovich) ya no son respuestas válidas.

Kunal
fuente
Tal vez reformule la pregunta para abordar esto.
Derrick Stolee
12

La teoría combinatoria / numérica aditiva se usó mucho en la literatura sobre extractores. Creo que las primeras instancias provienen de notar que los gráficos de Paley podrían usarse como buenos extractores, y algunas preguntas abiertas en la teoría de números aditivos implicarían mejores. La referencia más antigua que conozco es Zuckerman 1990 (ver su tesis ), pero en los últimos años ha sido un área activa con interesantes entre TCS y la combinatoria aditiva. (Uno de los aspectos más destacados es la prueba de Dvir de la conjetura de Kakeya de campo finito, pero esto es, por supuesto, una contribución de TCS a las matemáticas y no al revés). A priori no está claro por qué este tipo de preguntas matemáticas, sobre sumas y productos de conjuntos, sería importante para CS.

Boaz Barak
fuente
66
Otro buen ejemplo en este sentido es el uso reciente de la conjetura de densidad de Hales-Jewitt para probar un límite inferior no lineal en la red épsilon para un espacio de rango de VC dimensión 2.
Suresh Venkat
11

Sleator, Tarjan y Thurston demostraron la existencia de una familia infinita de pares de árboles de búsqueda binarios con nvértices y distancia de rotación 2n-6utilizando geometría hiperbólica.

zotachidil
fuente
7

o(k2)

k2

Álgebra lineal utilizada para esparcir gráficos:

Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava: Sparsifiers Twice-ramanujan. STOC 2009: 255-262.

Jelani Nelson
fuente
6

Esto puede o no contar, pero recientemente se han aplicado las teorías de Zermelo-Fraenkel con átomos (ZFA) y Fraenkel-Mostowski (FM) al estudio de la sintaxis abstracta con enlace de nombre. ZFA se introdujo a principios del siglo XX como una herramienta para demostrar la independencia de CH y luego se olvidó, pero fue redescubierto a fines de la década de 1990 por dos informáticos, Gabbay y Pitts, que estudiaban algo completamente desconectado.

Vea este documento de encuesta, por ejemplo.

Dominic Mulligan
fuente
4

La aplicación de Kahn y Kim de la entropía gráfica a la clasificación bajo información parcial (http://portal.acm.org/citation.cfm?id=129731). Le dieron el primer algoritmo de tiempo polinómico que realiza la información teóricamente óptima (hasta constantes) número de comparaciones. El artículo es un pequeño viaje de campo en matemáticas, utilizando algunos argumentos combinatorios clásicos, junto con geometría convexa, entropía gráfica y programación convexa. Existe un algoritmo más simple más reciente, pero todavía sabemos cómo analizarlo sin entropía gráfica.

Sasho Nikolov
fuente
3

La teoría de números se utilizó para desarrollar RSA y otros esquemas criptográficos de clave pública.

Antonio Valerio Miceli-Barone
fuente
0

El descubrimiento de la multiplicación de Karatsuba fue sorprendente.

usuario3493
fuente
2
Gauss no estaría de acuerdo.
Jeff el