In this dissertation, we investigate a number of geometric problems in different settings. We present lower bounds and approximation algorithms for geometric problems in sequential and distributed settings. For the sequential setting, we prove the first hardness of approximation results for the following problems: \begin{itemize} \item Red-Blue Geometric Set Cover is APX-hard when the objects are axis-aligned rectangles. \item Red-Blue Geometric Set Cover cannot be approximated to within $2^{\log^{1-1/{(\log\log m)^c}}m}$ in polynomial time for any constant $c < 1/2$, unless $P=NP$, when the given objects are $m$ triangles or convex objects. This shows that Red-Blue Geometric Set Cover is a harder problem than Geometric Set Cover for some class of objects. \item Boxes Class Cover is APX-hard. \end{itemize} We also define MaxRM-3SAT, a restricted version of Max3SAT, and we prove that this problem is APX-hard. This problem might be interesting in its own right.\\ In the distributed setting, we define a new model, the fixed-link model, where each processor has a position on the plane and processors can communicate to each other if and only if there is an edge between them. We motivate the model and study a number of geometric problems in this model. We prove lower bounds on the communication complexity of the problems in the fixed-link model and present approximation algorithms for them. We prove lower bounds on the number of expected bits required for any randomized algorithm in the fixed-link model with $n$ nodes to solve the following problems, when the communication is in the asynchronous KT1 model: \begin{itemize} \item $\Omega(n^2/\log n)$ expected bits of communication are required for solving Diameter, Convex Hull, or Closest Pair, even if the graph has only a linear number of edges. \item $\Omega( min\{n^2,1/\epsilon\})$ expected bits of communications are required for approximating Diameter within a $1-\epsilon$ factor of optimal, even if the graph is planar. \item $\Omega(n^2)$ bits of communications is required for approximating Closest Pair in a graph on an $[n^c] \times [n^c]$ grid, for any constant $c>1+1/(2\lg n)$, within $\frac{n^{c-1/2}}{4}-\epsilon$ factor of optimal, even if the graph is planar. \end{itemize} We also present approximation algorithms in geometric communication networks with $n$ nodes, when the communication is in the asynchronous CONGEST KT1 model: \begin{itemize} \item An $\epsilon$-kernel, and consequently $(1-\epsilon)$-\diamapprox~ and \ep -Approximate Hull with $O(\frac{n}{\sqrt{\epsilon}})$ messages plus the costs of constructing a spanning tree. \item An $\frac{n^c}{\sqrt{\frac{k}{2}}}$-Approximate Closest Pair on an $[n^c] \times [n^c]$ grid , for a constant $c>1/2$, plus the cost of computing a spanning tree, for any $k\leq {n-1}$. \end{itemize} We also define a new version of the two-party communication problem, Path Computation, where two parties communicate through a path. We prove a lower bound on the communication complexity of this problem. / Graduate

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.

No description available.