Análisis complejo en informática teórica.

24

Existen muchas aplicaciones de análisis real en ciencias de la computación teóricas, que abarcan las pruebas de propiedad, la complejidad de la comunicación, el aprendizaje PAC y muchos otros campos de investigación. Sin embargo, no puedo pensar en ningún resultado en TCS que se base en análisis complejos (fuera de la computación cuántica, donde los números complejos son intrínsecos en el modelo). ¿Alguien tiene un ejemplo de un resultado TCS clásico que utiliza análisis complejo?

soft-question big-picture
fuente

1

Gran pregunta! Sugeriría que sería mejor excluir los resultados relacionados con la teoría de números, por ejemplo, cualquier uso de la hipótesis de Riemann, en lugar de la computación cuántica, que tiende a ser sobre sistemas de dimensiones finitas (que yo sepa).

Colin McQuillan

11

Usamos el análisis complejo en un artículo "La constante de Grothendieck es estrictamente más pequeña que el límite de Krivine", que (desde el punto de vista de TCS) proporciona un algoritmo de aproximación para el problema de maximizar sujeto a . Ver ttic.uchicago.edu/~yury/papers/grothendieck-krivine.pdf

\sum_{i, j} a_{i j} x_{i} y_{j}

$\sum_{i,j} a_{ij} x_i y_j$

x_{i}, y_{j} \in {\pm 1}

$x_i, y_j\in \{\pm 1\}$

Yury el

3

@Yury que bien podría ser una respuesta.

Suresh Venkat

14

El algoritmo basado en el complejo de Barvinok para aproximar los algoritmos de tiempo polinómico permanente para aproximar permanentes y discriminantes mixtos dentro de un factor simplemente exponencial .

Además, obviamente, los operadores complejos (y algunos análisis complejos) son importantes en la computación cuántica.

Permítanme recomendar también este libro: Temas en el análisis de rendimiento de Eitan Bachmat con muchos temas relevantes y otras cosas geniales.

Gil Kalai
fuente

Ese es un gran ejemplo, no estaba al tanto de este resultado, ¡gracias!

25

No es un problema único, pero todo el campo de la combinatoria analítica (ver el libro de Flajolet y Sedgewick ) explora cómo analizar la complejidad combinatoria de las estructuras de ~~conteo~~ (o incluso los tiempos de ejecución de algoritmos) escribiendo una función de generación apropiada y analizando la estructura de las soluciones complejas.

Suresh Venkat
fuente

Hola Suresh, ¿qué quieres decir con 'analizar la complejidad'?

Andy Drucker el

2

Ah, escribí mal. Quise decir "analizar la complejidad combinatoria de las estructuras" - se solucionará.

Suresh Venkat

15

Jon Kelner ganó el premio STOC al mejor trabajo para estudiantes en 2004 por su trabajo "Partición espectral, límites de valores propios y empaques circulares para gráficos de género acotado"

Solo citaré del resumen:

Como nuestro lema técnico principal, probamos un O (g / n) unido al segundo valor propio más pequeño del Laplaciano de tales gráficos y mostramos que esto es ajustado, resolviendo así una conjetura de Spielman y Teng. Si bien este lema es esencialmente de naturaleza combinatoria, su prueba proviene de las matemáticas continuas, basándose en la teoría de los empaques circulares y la geometría de las superficies compactas de Riemann.

El uso de análisis complejos (y otras matemáticas "continuas") para atacar los problemas de separación de gráficos "tradicionales" fue memorable y es la razón principal por la que este documento se me quedó grabado en la cabeza, aunque no tiene ninguna relación con mi investigación.

Mugizi Rwebangira
fuente

8

Supongo que podría estar más interesado en el análisis complejo utilizado directamente en la prueba. Sin embargo, aquí hay dos ejemplos de una clase de Algoritmos de posgrado a la que estoy asistiendo actualmente:

a) Transformada rápida de Fourier, por ejemplo, utilizada en la multiplicación polinómica. Aunque la implementación se puede hacer con módulo aritmético o coma flotante (y algunos análisis aritméticos), la prueba se entiende mejor en términos de números complejos y sus raíces de unidad. No he profundizado en el tema, pero soy consciente de que FFT tiene una amplia gama de aplicaciones.

b) En general, equipar el modelo RAM con la capacidad de manejar números complejos en tiempo constante (las partes reales e imaginarias aún tienen precisión finita) le permite a uno codificar inteligentemente problemas y explotar las propiedades de los números complejos que podrían revelar una solución (ver también los comentarios de por qué esto no te permitirá ser más rápido).

chazisop
fuente

¿Tienes un ejemplo de la segunda observación? Es trivial agregar una clase "complejo O (log n) -bit entero" a la RAM estándar con operaciones de tiempo constante. O por "más rápido", ¿quiere decir "más rápido por un factor de 2"?

Jeffε

Este fue un ejercicio de la conferencia: "Suponga que está tratando con una RAM extendida que puede calcular con números complejos al costo unitario por multiplicación, división, suma y resta. Además, también puede calcular el valor absoluto | c | de un número complejo c en unidad de tiempo. Además, "conoce" las constantes complejas 0, 1 e I. Demuestre que dado un entero positivo n en una RAM tan extendida, el número n! puede calcularse en

tiempo. La solución usa la multiplicación polinómica, por lo que sé, esto es más rápido que el modelo RAM estándar.

O (\sqrt{n} \log^{2} n)

$O( \sqrt{n} \log ^{2} n)$

chazisop

66

El algoritmo propuesto requiere aritmética real de precisión infinita en tiempo constante. (¡No puede calcular un entero

-bit en

tiempo usando una máquina con palabras

-bit, porque ni siquiera tendría tiempo para anotar la salida!) La pregunta es pedirle que agregue raíces cuadradas al modelo RAM real, no números complejos per se.

Ω (n \log n)

$\Omega(n\log n)$

o (n)

$o(n)$

O (\log n)

$O(\log n)$

Jeffε

Gracias por el comentario, es muy esclarecedor. Creo que debería actualizar mi respuesta a la parte de solo codificar inteligentemente un problema con números complejos, es decir, para ver una solución que de lo contrario se perdería.

chazisop

6

Tal vez esta aplicación esté algo entre TCS y Matemáticas de disco, pero me sorprendió un poco cuando leí el artículo "Sobre las funciones booleanas dobladas que son simétricas" por Petr Savicky (http://www2.cs.cas.cz/~savicky/ papers / symmetric.ps). Los teoremas solo se refieren a funciones booleanas, sin embargo, una de las pruebas utiliza números complejos.

Magnus Find
fuente

5

Utilizamos el Teorema de los residuos de Cauchy del análisis complejo como la principal herramienta técnica en nuestro trabajo " Predicadores de umbral lineal aproximado ".

MCH
fuente

5

El teorema de empaquetamiento circular de Koebe-Andreev-Thurston se origina en el teorema de mapeo de Riemann y tiene varios aspectos algorítmicos. Por ejemplo, es una prueba del teorema del emperador Lipton-Tarjan para gráficos planos.

Gil Kalai
fuente

5

Fresco del horno:

Un algoritmo de tiempo polinómico para la recuperación de la población con pérdida Por: Ankur Moitra, Michael Saks

Citando el artículo: "Aquí demostraremos el principio de incertidumbre establecido en la sección anterior utilizando herramientas de análisis complejo. Quizás uno de los teoremas más útiles para comprender la tasa de crecimiento de las funciones holomórficas en el plano complejo es el Teorema de tres círculos de Hadamard. .. "

Gil Kalai
fuente

Permítanme dar un bosquejo rápido de cómo se usa el Teorema de los tres círculos en este documento. Para minimizar una cantidad

que satisface algunas restricciones lineales, observan el dual de este LP. Al ver las variables duales como coeficientes de un polinomio, esto se convierte en equivalente a maximizar

sobre todo grado

polys

satisfactorio

donde

es

compuesto con una transformación afín y

σ

$\sigma$

p (0) - ϵ ‖ p ‖_{1}

$p(0) - \epsilon \|p\|_1$

n

$n$

p

$p$

‖ q ‖_{1} \leq 1

$\|q\|_1 \leq 1$

q

$q$

p

$p$

‖ \cdot ‖_{1}

$\|\cdot\|_1$ denota la suma del valor abs de los coeficientes.

arnab

(cont.) Ahora, la bella observación es que

donde

es la unidad de disco en el plano complejo de radio 1. Si usamos esta relajación, el problema se reduce a maximizando

sujeto a que

esté limitado por

sobre un disco más pequeño dentro de

‖ p ‖_{1} \geq ‖ p ‖_{s u p}^{D_{1}}

$\|p\|_1 \geq \|p\|_{sup}^{D_1}$

D_{1}

$D_1$

p (0) - ‖ p ‖_{s u p}^{D_{1}}

$p(0) - \|p\|_{sup}^{D_1}$

p

$p$

1

$1$

D_{1}

$D_1$ . Haciendo una transformación de coordenadas, nos encontramos en la configuración del teorema de los Tres Círculos: una función holomórfica está limitada a puntos en dos círculos concéntricos, delimitando la función en cualquier círculo de radio intermedio.

arnab

‖ p ‖_{s u p}^{D_{1}} \geq | p (0) |^{Ω (1)}

$\|p\|_{sup}^{D_1} \geq |p(0)|^{\Omega(1)}$

p

$p$

1

$1$

D_{1}

$D_1$

5

$\ell_p$ $0 < p < 2$

Daniel M. Kane, Jelani Nelson, David P. Woodruff. Sobre la complejidad espacial exacta de dibujar y transmitir pequeñas normas. SODA 2010.

Puede salirse con la suya escribiendo una prueba que no mencione el análisis complejo explícitamente (vea la primera viñeta en la sección de "notas" para ese documento en mi página web), pero incluso esa prueba tiene un análisis complejo al acecho debajo de las cubiertas.

Jelani Nelson
fuente

4

En un artículo reciente de Naor, Regev y Vidick se utilizan números complejos y análisis, que arrojan resultados en algoritmos de aproximación para problemas de optimización NP-hard: http://arxiv.org/abs/1210.7656

Clemente C.
fuente

Otro artículo que utiliza raíces aleatorias de la unidad es Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald y He Sun. Recuento de subgrafías arbitrarias en flujos de datos. ICALP 2012.

Jelani Nelson

3

$n + O(n/\sqrt{k})$ $k$ $n \times n$ $n!/n^n$ por Laurent y Schrijver en el MAA Monthly). Dejar la línea real para el plano complejo parece esencial para la prueba de Gurvits y simplifica mucho las cosas.

Sasho Nikolov
fuente

0

$z \leftarrow z^2 + c$

[1] Inaccesibilidad e indecidibilidad en computación, geometría y sistemas dinámicos Asaki Saito, Kunihiko Kaneko

[2] Una teoría de la computación y la complejidad sobre los números reales Lenore Blum, 1990

vzn
fuente

0

$\mathbb{C}$

Cabina Reb.
fuente

Análisis complejo en informática teórica.

Respuestas: