Dissertations / Theses on the topic 'Ensembles somme'

Dans le cadre discrétisé, la taille d'un ensemble à l'échelle δ est évaluée par son nombre de recouvrement par δ-boules (également connu sous le nom de l'entropie métrique). Dans cette thèse, nous étudions les propriétés combinatoires des ensembles discrétisés sous l'addition, la multiplication et les projections orthogonales. Il y a trois parties principales. Premièrement, nous démontrons un théorème somme-produit dans les algèbres de matrices, qui généralise un théorème somme-produit de Bourgain concernant l'anneau des réels. On améliore aussi des estimées somme-produit en dimension supérieure obtenues précédemment par Bougain et Gamburd. Deuxièmement, on étudie les projections orthogonales des sous-ensembles de l'espace euclidien et étend ainsi le théorème de projection discrétisé de Bourgain aux projections de rang supérieur. Enfin, dans un travail en commun avec Nicolas de Saxcé, nous démontrons un théorème produit dans les groupes de Lie parfaits. Ce dernier résultat généralise les travaux antérieurs de Bourgain-Gamburd et de Saxcé
In the discretized setting, the size of a set is measured by its covering number by δ-balls (a.k.a. metric entropy), where δ is the scale. In this document, we investigate combinatorial properties of discretized sets under addition, multiplication and orthogonal projection. There are three parts. First, we prove sum-product estimates in matrix algebras, generalizing Bourgain's sum-product theorem in the ring of real numbers and improving higher dimensional sum-product estimates previously obtained by Bourgain-Gamburd. Then, we study orthogonal projections of subsets in the Euclidean space, generalizing Bourgain's discretized projection theorem to higher rank situations. Finally, in a joint work with Nicolas de Saxcé, we prove a product theorem for perfect Lie groups, generalizing previous results of Bourgain-Gamburd and Saxcé

Réalisé en cotutelle avec l'Université Paris-Diderot.
Nous présentons trois résultats en combinatoire additive, un domaine récent à la croisée de la combinatoire, l'analyse harmonique et la théorie analytique des nombres. Le thème unificateur de notre thèse est la détection de structures additives dans les ensembles arithmétiques à faible densité, avec un intérêt particulier pour les aspects quantitatifs. Notre première contribution est une estimation de densité améliorée pour le problème, initié entre autres par Bourgain, de trouver une longue progression arithmétique dans un ensemble somme triple. Notre deuxième résultat consiste en une généralisation des bornes de Sanders pour le théorème de Roth, du cas d'un ensemble dense dans les entiers à celui d'un ensemble à faible croissance additive dans un groupe abélien arbitraire. Finalement, nous étendons les meilleures bornes quantitatives connues pour le théorème de Roth dans les premiers, à tous les systèmes d'équations linéaires invariants par translation et de complexité un.
We present three results in additive combinatorics, a recent field at the interface of combinatorics, harmonic analysis and analytic number theory. The unifying theme in our thesis is the detection of additive structure in arithmetic sets of low density, with an emphasis on quantitative aspects. Our first contribution is an improved density estimate for the problem, initiated by Bourgain and others, of finding a long arithmetic progression in a triple sumset. Our second result is a generalization of Sanders' bounds for Roth's theorem from the dense setting, to the setting of small doubling in an arbitrary abelian group. Finally, we extend the best known quantitative results for Roth's theorem in the primes, to all translation-invariant systems of equations of complexity one.

Le premier volet de cette thèse porte sur l'étude de graphes dont les sommets sont colorés. Nous étudions comment la recherche d'ensembles particuliers de sommets est affectée lorsqu'on ajoute la contrainte qu'ils soient tropicaux, c'est à dire contiennent au moins un sommet de chacune des couleurs.Cette contrainte additionnelle tend à fortement augmenter la complexité des problèmes. Par exemple, la recherche d'un plus petit ensemble dominant tropical, et celle d'une plus petite couverture par sommet tropicale, sont APX-complets même restreints aux chemins. La recherche du plus petit sous-graphe connexe tropical d'un graphe est elle NP-complète, même restreinte aux arbres. Cependant, ajouter un contrainte sur le nombre de couleurs permet souvent de réduire la complexité. Par exemple, sans restrictions sur le type de graphes en entrée, la recherche d'un sous-graphe connexe tropical s'effectue en temps polynomial pourvu que le nombre de couleurs reste logarithmique en la taille du graphe. De plus, nous montrons divers résultats structurels qui lient la taille d'un sous-graphe connexe tropical minimum à des paramètres du graphe tels que le nombre de couleurs, le nombre d'arêtes, le degré minimum, ... Dans le second volet, nous étudions des jeux sur des graphes, appelés jeux de défense, où des attaquants ciblent des sommets et des défenseurs protègent des sous-graphes. On s'intéresse à l'existence d'un équilibre de Nash lorsque les défenseurs protègent des chemins de taille au plus p. Lorsque chaque défenseur protège exactement une arête, nous montron
The first pane of this thesis is on the study of vertex-colored graphs. We look at the tractability of asserting the existence of particular sets of vertices on a graph with the added constraint that the sets must be tropical, i.e. they must contain at least one vertex of each of the colors in the graph.This additional constraint tends to make the problems way less tractable. For instance, finding a minimum tropical dominating set, or a minimum tropical vertex cover, are APX-complete problems even when restricted to paths. Finding the smallest tropical connected subgraph is also NP-complete even when restricted to trees. However, restricting the number of colors will usually make problems more tractable. For instance, finding a connected tropical subgraph (on any graph) can be done in polynomial time as long as the number of colors is logarithmic in the size of the graph. Moreover, we show some structural results that links the size of a minimum connected subgraph to parameters such as the number of colors, the number of edges, the minimum degree…The second pane is on the study of some games on graphs, called defense games, in which multiple attackers target vertices and multiple defenders protect subgraphs.We focus on the existence of a Nash equilibrium when defenders protect paths of size at most p.When each defender protects exactly one edge, we show among other results that the game on a graph G with n defenders and k attackers admits a Nash equilibrium if and only if there exists a dominating set of size at most k in G, which is NP-complete in the general case.Similarly, when each defender protects a path of size at most p, the existence of a Nash equilibrium is linked to the notion of p-independent, i.e. a set of vertices such that every pair of elements of the set is at distance greater than p.Determining the existence of a maximal p-independent of size at most k is NP-complete, but our Min2stablemax algorithm can compute the minimum size of a maximal 2-independent set in a tree

Le but de ce travail est d'étudier la notion d'amibe (dans le sens de Favorov) pour un système F des sommes d'exponentielles de n-variables complexes et à fréquences réelles génériques. À l'aide d'une perturbation par caractères du groupe des fréquences de F, on obtient une expression de l'amibe de F qui nous permet d'en étudier la topologie. En particulier on montre que, si F est constitué par (k+1) éléments, le complémentaire de l'amibe de F est un sous-ensemble k-convexe de R^n. Ce résultat généralise l'analogue algébrique montré par Henriques. En outre, dans le cas d'une seule somme d'exponentielles f, on envisage les rapports entre l'amibe de f et sa fonction de Ronkin
The aim of this work is to study the notion of amoeba (in the sense of Favorov) for a system F of exponential sums of n complex variables and real generic frequencies. Thanks to a perturbation by characters of the group of frequencies of F, we obtain a expression of the amoeba of F which is useful in the study of its topology. In particular, we show that, if F has (k+1) elements, the complementary set to the amoeba of F is a k-convex subset of R^n in Henriques' sense. This result generalize the algebraic analog shown by Henriques. Moreover, in the case of one exponential sum f, we investigate the relations between the amoeba of f and its Ronkin function

Etendant le resultat de jarnik, nous montrons que pour toute fonction x tendant vers l'infini, il est possible de construire une courbe strictement convexe c telle que l'intersection de c et du reseau (1/q z)2 contienne plus d'une constante fois q2/3/x(q) elements, et ceci pour une infinite de valeurs de q. Nous montrons aussi comment, grace a des methodes provenant de la theorie analytique des nombres, on peut etendre les travaux de freiman, sur les sommes de sous-ensembles en dimension 2. Independamment, on caracterise tres precisement les sous-ensembles de (z/2z)n ayant un petit double. Enfin, nous nous interessons aux bornes inferieures pour le cardinal d'un code de rayon de recouvrement donne r dans l'espace f#n#q. Nous obtenons un grand nombre de nouvelles bornes, ameliorant ainsi pres de 20% des cas etudies par la litterature.

Cette thèse étudie quelques problèmes d’analyse harmonique sur les groupes quantiques compacts. Elle consiste en trois parties. La première partie présente la théorie Lp élémentaire des transformées de Fourier, les convolutions et les multiplicateurs sur les groupes quantiques compacts, y compris la théorie de Hausdorff-Young et les inégalités de Young.Dans la seconde partie, nous caractérisons les opérateurs de convolution positifs sur un groupe quantique fini qui envoient Lp dans L2, et donnons aussi quelques constructions sur les groupes quantiques compacts infinis. La méthode pour étudier les états non-dégénérés fournit une formule générale pour calculer les états idempotents associés aux images deHopf, qui généralise un travail de Banica, Franz et Skalski. La troisième partie est consacrée à l’étude des ensembles de Sidon, des ensembles _(p) et des notions associées pour les groupes quantiques compacts. Nous établissons différentes caractérisations des ensembles de Sidon, et en particulier nous démontrons que tout ensemble de Sidon est un ensemble de Sidon fort au sens de Picardello. Nous donnons quelques liens entre les ensembles de Sidon, les ensembles _(p) et les lacunarités pour les multiplicateurs de Fourier sur Lp, généralisant un travail de Blendek et Michali˘cek. Nous démontrons aussi l’existence des ensembles de type _(p) pour les systèmes orthogonaux dans les espaces Lp non commutatifs, et déduisons les propriétés correspondantes pour les groupes quantiques compacts. Nous considérons aussi les ensembles de Sidon centraux, et nous prouvons que les groupes quantiques compacts ayant les mêmes règles de fusion et les mêmes fonctions de dimension ont des ensemble de Sidon centraux identiques. Quelques exemples sont aussi étudiés dans cette thèse. Les travaux présentés dans cette thèse se basent sur deux articles de l’auteur. Le premier s’intitule “Lp-improving convolution operators on finite quantum groups” et a été accepté pour publication dans Indiana University Mathematics Journal, et le deuxième est un travail intitulé “Lacunary Fourier series for compact quantum groups” et a été publié en ligne dans Communications in Mathematical Physics
This thesis studies some problems in the theory of harmonic analysis on compact quantum groups. It consists of three parts. The first part presents some elementary Lp theory of Fourier transforms, convolutions and multipliers on compact quantum groups, including the Hausdorff-Young theory and Young’s inequalities. In the second part, we characterize positive convolution operators on a finite quantum group G which are Lp-improving, and also give some constructions on infinite compact quantum groups. The methods for ondegeneratestates yield a general formula for computing idempotent states associated to Hopf images, which generalizes earlier work of Banica, Franz and Skalski. The third part is devoted to the study of Sidon sets, _(p)-sets and some related notions for compact quantum groups. We establish several different characterizations of Sidon sets, and in particular prove that any Sidon set in a discrete group is a strong Sidon set in the sense of Picardello. We give several relations between Sidon sets, _(p)-sets and lacunarities for Lp-Fourier multipliers, generalizing a previous work by Blendek and Michali˘cek. We also prove the existence of _(p)-sets for orthogonal systems in noncommutative Lp-spaces, and deduce the corresponding properties for compact quantum groups. Central Sidon sets are also discussed, and it turns out that the compact quantum groups with the same fusion rules and the same dimension functions have identical central Sidon sets. Several examples are also included. The thesis is principally based on two works by the author, entitled “Lp-improvingconvolution operators on finite quantum groups” and “Lacunary Fourier series for compact quantum groups”, which have been accepted for publication in Indiana University Mathematics Journal and Communications in Mathematical Physics respectively

Differents modes de convergence sont etudies pour des sommes d'ensembles aleatoires independants a valeurs convexes fermes bornes. On definit la fonction caracteristiques d'un ensemble aleatoire et on etudie ses proprietes. Une topologie, introduite par beer, est etudiee sur l'ensemble des parties convexes fermees bornees d'un espace de banach separable. Elle est moins fine que la topologie de hausdorff et plus fine que la topologie de mosco. Plusieurs theoremes de convergence de martingales multivoques sont donnes

Dans cette thèse, on s'intéresse à l'étude d'existence de solutions pour les processus de rafle. Ce problème prend la forme d'une inclusion différentielle contrainte avec des cônes normaux qui apparaissent naturellement dans nombreuses applications telles que le mouvement de foule, l'élastoplasticité, les mécaniques, les circuits électroniques, etc. L'objective de ce travail est de rapprocher deux importantes classes d'inclusions différentielles. D'une part, nous établissons quelques résultats d'existence de tube-solutions pour des processus de rafle à des ensembles uniformément prox-réguliers. D'autre part, nous présentons des résultats d'existence de solutions monotone par rapport à un préordre pour un système mixte d'inclusions différentielles projetées. De plus, nous montrons l'existence d'un point-selle pour notre système et nous fournissons deux exemples d'applications
In this thesis, we were interested in the study of the existence of solutions for sweeping processes. This problem takes the form of a constrained differential inclusion involving normal cones which appears naturally in many applications such as crowd motion, elastoplasticity, mechanics, electrical circuit, etc.The aim of this work is to bring together two classes of differential inclusions. On one hand, we establish some existence results of solutions-tube for sweeping processes with uniformly prox-regular sets. On the other hand, we present existence results of monotone solutions with respect to a preorder for a mixed system of projected differential inclusions. In addition, we show that our system has a saddle-point and we provide two examples of applications

Cette thèse est consacrée à l'étude du problème de la cyclicité dans certains espaces de fonctions analytiques sur le disque unité. Nous nous intéressons aux espaces de type Bergman et aux espaces de type Korenblum. Dans la première partie, nous étudions les fonctions cycliques dans les espaces de type Korenblum en utilisant la notion des prémesures. Cette notion a été introduite et développée par B. Korenblum au début des années 1970s. En particulier, nous donnons une réponse positive à une conjecture énoncée par C. Deninger. Dans la deuxième partie, nous utilisons la méthode de la résolvante pour étudier la cyclicité des fonctions intérieures singulières associées aux mesures de Dirac dans les espaces de type Bergman à poids
In this thesis, we study the cyclicity problem in some spaces of analytic functions on the open unit disc. We focus our attention on Korenblum type spaces and on weighted Bergman type spaces. First, we use the technique of premeasures, introduced and developed by Korenblum in the 1970-s and the 1980-s, to give a characterization of cyclic functions in the Korenblum type spaces. In particular, we give a positive answer to a conjecture by Deninger. Second, we use the so called resolvent transform method to study the cyclicity of the one point mass singular inner function in weighted Bergman type spaces, especially with weights depending on the distance to a subset of the unit circle

Dans un avion, un hélicoptère ou un lanceur actuel, des milliers de capteurs, pour la plupart non critiques sont utilisés pour la mesure de divers paramètres (températures, pressions, positions...) Les résultats sont ensuite acheminés par des fils vers les calculateurs de bord qui les traitent. Ceci implique la mise en place de centaines de kilomètres de câbles (500 km pour un avion de ligne) dont le volume est considérable. Il en résulte une grande complexité de conception et de fabrication, des problèmes de fiabilité, notamment au niveau des connexions, et une masse importante. Par ailleurs l'instrumentation de certaines zones est impossible car leur câblage est difficilement envisageable par manque d'espace. En outre, s'il est souvent intéressant d'installer de nouveaux capteurs pour faire évoluer un aéronef ancien, l'installation des câbles nécessaires implique un démantèlement partiel, problématique et coûteux, de l'appareil. Pour résoudre ces problèmes, une idée innovante a émergé chez les industriels de l'aéronautique : commencer à remplacer les réseaux filaires reliant les capteurs d'un aéronef et leur centre de décision par des réseaux sans fil. Les technologies de communication sans fil sont aujourd'hui largement utilisées dans les marchés de l'électronique de grande consommation. Elles commencent également à être déployées pour des applications industrielles comme l'automobile ou le relevé à distance de compteurs domestiques. Cependant, remplacer des câbles par des ondes représente un défi technologique considérable comme la propagation en milieu confiné, la sécurité, la sureté de fonctionnement, la fiabilité ou la compatibilité électromagnétique. Cette thèse est motivée d'une part par l'avancée non négligeable dans le milieu aérospatial que pourrait être l'établissement d'un réseau sans fil à bord d'aéronefs dans la résolution de problématique classiques comme l'allégement et l'instrumentation. Il en résulterait donc : * Une meilleure connaissance de l'environnement et de la santé de l'aéronef * Un gain sur le poids. * Un gain en flexibilité. * Un gain en malléabilité et en évolutivité. * Un gain sur la complexité. * Un gain sur la fiabilité D'autre part, étant donnée la complexité de la conception de ce réseau de capteur sans fil, il a été nécessaire d'appliquer une méthodologie évolutive et adaptée mais inspirée de l'ingénierie système. Il est envisageable, vu le nombre de sous-systèmes à considérer, que cette méthodologie soit réutilisable pour d'autre cas pratiques. Une étude aussi complète que possible a été réalisée autour de l'existant déjà établi sur le sujet. En effet, on peut en lisant ce mémoire de thèse avoir une idée assez précise de ce qui a été fait. Une liste a été dressée de toutes les technologies sans fil en indiquant leur état de maturité, leurs avantages et leurs inconvénients afin de préciser les choix possibles et les raisons de ces choix. Des projets de capteurs sans fil ont été réalisés, des technologies sans fil performantes et personnalisables ont été développées et arrivent à maturité dans des secteurs variés tels que la domotique, la santé, l'automobile ou même l'aéronautique. Cependant aucun capteur sans fil n'a été véritablement installé en milieu aérospatial car de nombreux verrous technologiques n'ont pas été levés. Fort des expériences passées, et de la maturité qu'ont prise certaines technologies, des conclusions ont été tirées des projets antérieurs afin de tendre vers des solutions plus viables. Une fois identifiés, les verrous technologiques ont été isolés. Une personnalisation de notre solution a été à envisager afin de remédier tant que faire se peut à ces points bloquants avec les moyens mis à disposition. La méthodologie appliquée nous a permis d'identifier un maximum de contraintes, besoins et exigences pour mieux focaliser les efforts d'innovation sur les plus importantes et choisir ainsi les technologies les plus indiquées.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-01T21:11:37Z No. of bitstreams: 1 REX ANTONIO DA COSTA MEDEIROS - TESE PPGEE 2008..pdf: 1089371 bytes, checksum: ea0c95501b938e0d466779a06faaa4f6 (MD5)
Made available in DSpace on 2018-08-01T21:11:37Z (GMT). No. of bitstreams: 1 REX ANTONIO DA COSTA MEDEIROS - TESE PPGEE 2008..pdf: 1089371 bytes, checksum: ea0c95501b938e0d466779a06faaa4f6 (MD5) Previous issue date: 2008-05-09
Nesta tese, a capacidade erro-zero de canais discretos sem memória é generalizada para canais quânticos. Uma nova capacidade para a transmissão de informação clássica através de canais quânticos é proposta. A capacidade erro-zero de canais quânticos (CEZQ) é definida como sendo a máxima quantidade de informação por uso do canal que pode ser enviada através de um canal quântico ruidoso, considerando uma probabilidade de erro igual a zero. O protocolo de comunicação restringe palavras-código a produtos tensoriais de estados quânticos de entrada, enquanto que medições coletivas entre várias saídas do canal são permitidas. Portanto, o protocolo empregado é similar ao protocolo de Holevo-Schumacher-Westmoreland. O problema de encontrar a CEZQ é reformulado usando elementos da teoria de grafos. Esta definição equivalente é usada para demonstrar propriedades de famílias de estados quânticos e medições que atingem a CEZQ. É mostrado que a capacidade de um canal quântico num espaço de Hilbert de dimensão d pode sempre ser alcançada usando famílias compostas de, no máximo,d estados puros. Com relação às medições, demonstra-se que medições coletivas de von Neumann são necessárias e suficientes para alcançar a capacidade. É discutido se a CEZQ é uma generalização não trivial da capacidade erro-zero clássica. O termo não trivial refere-se a existência de canais quânticos para os quais a CEZQ só pode ser alcançada através de famílias de estados quânticos não-ortogonais e usando códigos de comprimento maior ou igual a dois. É investigada a CEZQ de alguns canais quânticos. É mostrado que o problema de calcular a CEZQ de canais clássicos-quânticos é puramente clássico. Em particular, é exibido um canal quântico para o qual conjectura-se que a CEZQ só pode ser alcançada usando uma família de estados quânticos não-ortogonais. Se a conjectura é verdadeira, é possível calcular o valor exato da capacidade e construir um código de bloco quântico que alcança a capacidade. Finalmente, é demonstrado que a CEZQ é limitada superiormente pela capacidade de Holevo-Schumacher-Westmoreland.

La théorie de l'information quantique s'est développée à une vitesse fulgurante au cours des vingt dernières années, avec des analogues et extensions des théorèmes de codage de source et de codage sur canal bruité pour la communication unidirectionnelle. Pour la communication interactive, un analogue quantique de la complexité de la communication a été développé, pour lequel les protocoles quantiques peuvent performer exponentiellement mieux que les meilleurs protocoles classiques pour certaines tâches classiques. Cependant, l'information quantique est beaucoup plus sensible au bruit que l'information classique. Il est donc impératif d'utiliser les ressources quantiques à leur plein potentiel. Dans cette thèse, nous étudions les protocoles quantiques interactifs du point de vue de la théorie de l'information et étudions les analogues du codage de source et du codage sur canal bruité. Le cadre considéré est celui de la complexité de la communication: Alice et Bob veulent faire un calcul quantique biparti tout en minimisant la quantité de communication échangée, sans égard au coût des calculs locaux. Nos résultats sont séparés en trois chapitres distincts, qui sont organisés de sorte à ce que chacun puisse être lu indépendamment. Étant donné le rôle central qu'elle occupe dans le contexte de la compression interactive, un chapitre est dédié à l'étude de la tâche de la redistribution d'état quantique. Nous prouvons des bornes inférieures sur les coûts de communication nécessaires dans un contexte interactif. Nous prouvons également des bornes atteignables avec un seul message, dans un contexte d'usage unique. Dans un chapitre subséquent, nous définissons une nouvelle notion de complexité de l'information quantique. Celle-ci caractérise la quantité d'information, plutôt que de communication, qu'Alice et Bob doivent échanger pour calculer une tâche bipartie. Nous prouvons beaucoup de propriétés structurelles pour cette quantité, et nous lui donnons une interprétation opérationnelle en tant que complexité de la communication quantique amortie. Dans le cas particulier d'entrées classiques, nous donnons une autre caractérisation permettant de quantifier le coût encouru par un protocole quantique qui oublie de l'information classique. Deux applications sont présentées: le premier résultat général de somme directe pour la complexité de la communication quantique à plus d'une ronde, ainsi qu'une borne optimale, à un terme polylogarithmique près, pour la complexité de la communication quantique avec un nombre de rondes limité pour la fonction « ensembles disjoints ». Dans un chapitre final, nous initions l'étude de la capacité interactive quantique pour les canaux bruités. Étant donné que les techniques pour distribuer de l'intrication sont bien étudiées, nous nous concentrons sur un modèle avec intrication préalable parfaite et communication classique bruitée. Nous démontrons que dans le cadre plus ardu des erreurs adversarielles, nous pouvons tolérer un taux d'erreur maximal de une demie moins epsilon, avec epsilon plus grand que zéro arbitrairement petit, et ce avec un taux de communication positif. Il s'ensuit que les canaux avec bruit aléatoire ayant une capacité positive pour la transmission unidirectionnelle ont une capacité positive pour la communication interactive quantique. Nous concluons avec une discussion de nos résultats et des directions futures pour ce programme de recherche sur une théorie de l'information quantique interactive.
Quantum information theory has developed tremendously over the past two decades, with analogues and extensions of the source coding and channel coding theorems for unidirectional communication. Meanwhile, for interactive communication, a quantum analogue of communication complexity has been developed, for which quantum protocols can provide exponential savings over the best possible classical protocols for some classical tasks. However, quantum information is much more sensitive to noise than classical information. It is therefore essential to make the best use possible of quantum resources. In this thesis, we take an information-theoretic point of view on interactive quantum protocols and study the interactive analogues of source compression and noisy channel coding. The setting we consider is that of quantum communication complexity: Alice and Bob want to perform some joint quantum computation while minimizing the required amount of communication. Local computation is deemed free. Our results are split into three distinct chapters, and these are organized in such a way that each can be read independently. Given its central role in the context of interactive compression, we devote a chapter to the task of quantum state redistribution. In particular, we prove lower bounds on its communication cost that are robust in the context of interactive communication. We also prove one-shot, one-message achievability bounds. In a subsequent chapter, we define a new, fully quantum notion of information cost for interactive protocols and a corresponding notion of information complexity for bipartite tasks. It characterizes how much quantum information, rather than quantum communication, Alice and Bob must exchange in order to implement a given bipartite task. We prove many structural properties for these quantities, and provide an operational interpretation for quantum information complexity as the amortized quantum communication complexity. In the special case of classical inputs, we provide an alternate characterization of information cost that provides an answer to the following question about quantum protocols: what is the cost of forgetting classical information? Two applications are presented: the first general multi-round direct-sum theorem for quantum protocols, and a tight lower bound, up to polylogarithmic terms, for the bounded-round quantum communication complexity of the disjointness function. In a final chapter, we initiate the study of the interactive quantum capacity of noisy channels. Since techniques to distribute entanglement are well-studied, we focus on a model with perfect pre-shared entanglement and noisy classical communication. We show that even in the harder setting of adversarial errors, we can tolerate a provably maximal error rate of one half minus epsilon, for an arbitrarily small epsilon greater than zero, at positive communication rates. It then follows that random noise channels with positive capacity for unidirectional transmission also have positive interactive quantum capacity. We conclude with a discussion of our results and further research directions in interactive quantum information theory.

La majorité des courbes et surfaces rencontrées dans la modélisation géométrique sont définies comme l'ensemble des solutions d'un système d'équations et d'inéquations algébriques (ensemble semi-algébrique). De nombreux problèmes dans différentes disciplines scientifiques font appel à des requètes de proximité telles que la recherche du ou des voisins les plus proches ou la quantification du voisinage de deux objets.

Le diagramme de Voronoï d'un ensemble d'objets est une décomposition de l'espace en zones de proximité. La zone de proximité d'un objet est l'ensemble des points plus proches de cet objet que de tout autre objet. Les diagrammes de Voronoï permettent de répondre aux requètes de proximité après avoir identifié la zone de proximité à laquelle le point objet de la requète appartient. Le graphe dual du diagramme de Voronoï est appelé le graphe de Delaunay. Seules les approximations par des coniques peuvent garantir un ordre de continuité approprié au niveau des points de contact, ce qui est nécessaire pour garantir l'exactitude du graphe de Delaunay.

L'objectif théorique de cette thèse est la mise en évidence des propriétés algébriques et géométriques élémentaires de la courbe déplacée d'une courbe algébrique et de réduire le calcul semi-algébrique du graphe de Delaunay à des calculs de valeurs propres. L'objectif pratique de cette thèse est le calcul certifié du graphe de Delaunay pour des ensembles semi-algébriques de faible degré dans le plan euclidien.

La méthodologie associe l'analyse par intervalles et la géométrie algébrique algorithmique. L'idée centrale de cette thèse est qu'un pré-traitement symbolique unique peut accélérer l'évaluation numérique certifiée du détecteur de conflits dans le graphe de Delaunay. Le pré-traitement symbolique est le calcul de l'équation implicite de la courbe déplacée généralisée d'une conique. La réduction du problème semi-algébrique de la détection de conflits dans le graphe de Delaunay à un problème d'algèbre linéaire a été possible grâce à la considération du sommet de Voronoï généralisé (un concept introduit dans cette thèse).

Le calcul numérique certifié du graphe de Delaunay a été éffectué avec une librairie de résolution de systèmes zéro-dimensionnels d'équations et d'inéquations algébriques basée sur l'analyse d'intervalles (ALIAS). Le calcul certifié du graphe de Delaunay repose sur des théorèmes sur l'unicité de racines dans des intervalles donnés (Kantorovitch et Moore-Krawczyk). Pour les coniques, les calculs sont accélérés lorsque l'on ne considère que les équations implicites des courbes déplacées.