Analyse complexe en informatique théorique

24

Il existe de nombreuses applications de l'analyse réelle en informatique théorique, couvrant les tests de propriété, la complexité de la communication, l'apprentissage PAC et de nombreux autres domaines de recherche. Cependant, je ne peux penser à aucun résultat dans TCS qui repose sur une analyse complexe (en dehors de l'informatique quantique, où les nombres complexes sont intrinsèques au modèle). Quelqu'un a-t-il un exemple d'un résultat TCS classique qui utilise une analyse complexe?

soft-question big-picture
la source

1

Grande question! Je dirais qu'il serait préférable d'exclure les résultats liés à la théorie des nombres - par exemple, toute utilisation de l'hypothèse de Riemann - plutôt que l'informatique quantique, qui tend à concerner les systèmes de dimension finie (pour autant que je sache).

Colin McQuillan

11

Nous utilisons une analyse complexe dans un article «La constante de Grothendieck est strictement plus petite que la limite de Krivine», qui (d'un point de vue TCS) donne un algorithme d'approximation pour le problème de la maximisation de

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

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

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

$x_i, y_j\in \{\pm 1\}$ . Voir ttic.uchicago.edu/~yury/papers/grothendieck-krivine.pdf

Yury

3

@Yury qui pourrait très bien être une réponse.

Suresh Venkat

14

Algorithme basé sur le complexe de Barvinok pour approximer les algorithmes de temps polynomiaux permanents pour approximer les discriminants permanents et mixtes dans un facteur simplement exponentiel .

De plus, évidemment, les opérateurs complexes (et certaines analyses complexes) sont importants en informatique quantique.

Permettez-moi de recommander également ce livre: Sujets en analyse de performance par Eitan Bachmat avec beaucoup de grandes questions pertinentes et bien d'autres choses.

Gil Kalai
la source

C'est un excellent exemple, je n'étais pas au courant de ce résultat - merci!

25

Ce n'est pas un problème unique, mais tout le domaine de la combinatoire analytique (voir le livre de Flajolet et Sedgewick ) explore comment analyser la complexité combinatoire des structures de ~~comptage~~ (ou même les temps d'exécution des algorithmes) en écrivant une fonction de génération appropriée et en analysant la structure des solutions complexes.

Suresh Venkat
la source

Salut Suresh, que veux-tu dire par "analyser la complexité"?

Andy Drucker

2

Ah j'ai mal écrit. Je voulais dire "analyser la complexité combinatoire des structures" - corrigera.

Suresh Venkat

15

Jon Kelner a remporté le STOC Best Student Paper Award en 2004 pour son article "Partitionnement spectral, limites de valeurs propres et emballages de cercles pour les graphiques du genre borné"

Je citerai simplement le résumé:

En tant que lemme technique principal, nous prouvons un O (g / n) lié à la deuxième plus petite valeur propre du laplacien de ces graphiques et montrons que cela est serré, résolvant ainsi une conjecture de Spielman et Teng. Bien que ce lemme soit essentiellement de nature combinatoire, sa preuve vient des mathématiques continues, s'appuyant sur la théorie des emballages de cercle et la géométrie des surfaces de Riemann compactes.

L'utilisation d'une analyse complexe (et d'autres mathématiques "continues") pour attaquer les problèmes de séparateurs de graphes "traditionnels" a été mémorable et est la principale raison pour laquelle ce document est resté dans ma tête même s'il n'a aucun lien avec mes recherches.

Mugizi Rwebangira
la source

8

Je suppose que vous pourriez être plus intéressé par une analyse complexe utilisée directement dans la preuve. Cependant, voici deux exemples d'une classe d'algorithmes de niveau supérieur que j'assiste actuellement:

a) Transformée de Fourier rapide, par exemple utilisée dans la multiplication polynomiale. Bien que l'implémentation puisse se faire avec modulo arithmétique ou virgule flottante (et certaines analyses arithmétiques), la preuve est mieux comprise en termes de nombres complexes et de leurs racines d'unité. Je ne me suis pas plongé dans le sujet, mais je suis conscient que la FFT a un large éventail d'applications.

b) En général, équiper le modèle RAM de la capacité de gérer des nombres complexes en temps constant (les parties réelles et imaginaires ont encore une précision finie) permet de coder intelligemment les problèmes et d'exploiter les propriétés des nombres complexes qui pourraient révéler une solution (voir aussi les commentaires pourquoi cela ne vous permettra pas d'être plus rapide).

chazisop
la source

Avez-vous un exemple de la deuxième observation? Il est trivial d'ajouter une classe "complexe O (log n) bits" à la RAM standard avec des opérations à temps constant. Ou par "plus vite", voulez-vous dire "plus vite par un facteur de 2"?

Jeffε

Il s'agissait d'un exercice de la conférence: "Supposons que vous avez affaire à une RAM étendue qui peut calculer des nombres complexes au coût unitaire par multiplication, division, addition et soustraction. De plus, il peut également calculer la valeur absolue | c | d'un nombre complexe c en unité de temps. De plus, il «connaît» les constantes complexes 0, 1 et i. Montrer que, étant donné un entier positif n sur une telle RAM étendue, le nombre n! peut être calculé dans

heure. La solution utilise la multiplication polynomiale, d'après ce que je sais, c'est plus rapide que le modèle de RAM standard.

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

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

chazisop

6

L'algorithme proposé nécessite une arithmétique réelle de précision infinie à temps constant. (Vous ne pouvez pas calculer un entier

bits en temps

utilisant une machine avec

Ω (n \log n)

$\Omega(n\log n)$

o (n)

$o(n)$

O (\log n)

$O(\log n)$ mots bits, car vous n'auriez même pas le temps d'écrire la sortie!) La question vous demande d'ajouter des racines carrées au modèle réel de RAM, et non des nombres complexes en soi.

Jeffε

Merci pour le commentaire, c'est très instructif. Je pense que je devrais mettre à jour ma réponse à la partie de l'encodage intelligent d'un problème avec des nombres complexes, c'est-à-dire pour voir une solution qui vous manquerait autrement.

chazisop

6

Peut-être que cette application est quelque peu entre TCS et Mathématiques du disque, mais j'ai été légèrement surpris en lisant l'article "Sur les fonctions booléennes courbées qui sont symétriques" par Petr Savicky (http://www2.cs.cas.cz/~savicky/ papiers / symmetric.ps). Les théorèmes ne concernent que les fonctions booléennes, cependant l'une des preuves utilise des nombres complexes.

Magnus Find
la source

5

Nous utilisons le théorème des résidus de Cauchy issu d'analyses complexes comme principal outil technique dans notre article " Approximation des seuils linéaires approximatifs ".

MCH
la source

5

Le théorème d'emballage de cercle de Koebe-Andreev-Thurston est originaire du théorème de cartographie de Riemann et présente divers aspects algorithmiques. Par exemple, il alloue une preuve du théorème de séparateur de Lipton-Tarjan pour les graphes planaires.

Gil Kalai
la source

5

Frais du four:

Un algorithme temporel polynomial pour la récupération de la population avec pertes Par: Ankur Moitra, Michael Saks

Citant l'article: "Ici, nous prouverons le principe d'incertitude énoncé dans la section précédente en utilisant des outils d'analyse complexe. Peut-être l'un des théorèmes les plus utiles pour comprendre le taux de croissance des fonctions holomorphes dans le plan complexe est le théorème des trois cercles d'Hadamard. .. "

Gil Kalai
la source

Permettez-moi de donner un bref aperçu de la façon dont le théorème des trois cercles est utilisé dans cet article. Afin de minimiser une quantité

qui satisfait certaines contraintes linéaires, ils regardent le dual de ce LP. En considérant les variables doubles comme des coefficients d'un polynôme, cela revient à maximiser

sur tous les degrés

polys

satisfaisant

où

est

composé d'une transformation affine et

σ

$\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$ désigne la somme de la valeur abs des coefficients.

arnab

(suite) Maintenant, la belle observation est que

où

est le disque unitaire dans le plan complexe du rayon 1. Si nous utilisons cette relaxation, le problème se résume à maximisation de

sous réserve que

soit limité par

sur un disque plus petit à l'intérieur 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$ . En faisant une transformation de coordonnées, nous nous trouvons dans le cadre du théorème des trois cercles: une fonction holomorphe est délimitée sur des points dans deux cercles concentriques, délimitant la fonction sur n'importe quel cercle de rayon intermédiaire.

arnab

(suite) Pour le problème, cela implique que

si

est borné par

sur un disque plus petit à l'intérieur de

. (Merci à un merveilleux discours de Mike Saks expliquant le papier.)

‖ 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$

arnab

5

Dans la section A.4 de cet article, nous utilisons une analyse complexe, ce qui nous conduit à une dérandomisation de l'algorithme d'Indyk pour l' estimation de dans les flux de données ( $\ell_p$ $0 < p < 2$ ) qui fournit des garanties d'espace optimales:

Daniel M. Kane, Jelani Nelson, David P. Woodruff. Sur la complexité spatiale exacte de l'esquisse et de la diffusion de petites normes. SODA 2010.

Vous pouvez vous en tirer en écrivant une preuve qui ne mentionne pas explicitement une analyse complexe (voir la première puce dans la section "notes" de ce document sur ma page Web), mais même cette preuve a une analyse complexe qui se cache sous les couvertures.

Jelani Nelson
la source

4

Il y a utilisation de nombres complexes et d'analyses dans un article récent de Naor, Regev et Vidick, donnant des résultats dans des algorithmes d'approximation pour des problèmes d'optimisation NP-hard: http://arxiv.org/abs/1210.7656

Clement C.
la source

Pourtant, un autre article qui utilise des racines aléatoires de l'unité est Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald et He Sun. Compter les sous-graphes arbitraires dans les flux de données. ICALP 2012.

Jelani Nelson

3

$n + O(n/\sqrt{k})$ $k$ $n \times n$ $n!/n^n$ . Les preuves d'Egorychev et Falikman ont utilisé des résultats profonds en géométrie convexe (en particulier l'inégalité Alexandrov-Fenchel). En revanche, une preuve récente de Gurvits n'utilise que des analyses élémentaires complexes et est tout à fait un bijou (belle présentation

Sasho Nikolov
la source

0

$z \leftarrow z^2 + c$

[1] Inaccessibilité et indécidabilité dans le calcul, la géométrie et les systèmes dynamiques Asaki Saito, Kunihiko Kaneko

[2] Une théorie du calcul et de la complexité sur les nombres réels Lenore Blum, 1990

vzn
la source

0

$\mathbb{C}$

Reb.Cabin
la source

Analyse complexe en informatique théorique

Réponses: