On Complexity of Lobbying in Multiple Referenda

In this paper we show that lobbying in conditions of “direct democracy” is virtually impossible, even in conditions of complete information about voters preferences, since it would require solving a very computationally hard problem. We use the apparatus of parametrized complexity for this purpose.

Structure de la distribution de probabilités de l'état GHZ sous l'action locale de transformations du groupe U(2)

Dans ce mémoire, je démontre que la distribution de probabilités de l'état quantique Greenberger-Horne-Zeilinger (GHZ) sous l'action locale de mesures de von Neumann indépendantes sur chaque qubit suit une distribution qui est une combinaison convexe de deux distributions. Les coefficients de la combinaison sont reliés aux parties équatoriales des mesures et les distributions associées à ces coefficients sont reliées aux parties réelles des mesures. Une application possible du résultat est qu'il permet de scinder en deux la simulation de l'état GHZ. Simuler, en pire cas ou en moyenne, un état quantique comme GHZ avec des ressources aléatoires, partagées ou privées, et des ressources classiques de communication, ou même des ressources fantaisistes comme les boîtes non locales, est un problème important en complexité de la communication quantique. On peut penser à ce problème de simulation comme un problème où plusieurs personnes obtiennent chacune une mesure de von Neumann à appliquer sur le sous-système de l'état GHZ qu'il partage avec les autres personnes. Chaque personne ne connaît que les données décrivant sa mesure et d'aucune façon une personne ne connaît les données décrivant la mesure d'une autre personne. Chaque personne obtient un résultat aléatoire classique. La distribution conjointe de ces résultats aléatoires classiques suit la distribution de probabilités trouvée dans ce mémoire. Le but est de simuler classiquement la distribution de probabilités de l'état GHZ. Mon résultat indique une marche à suivre qui consiste d'abord à simuler les parties équatoriales des mesures pour pouvoir ensuite savoir laquelle des distributions associées aux parties réelles des mesures il faut simuler. D'autres chercheurs ont trouvé comment simuler les parties équatoriales des mesures de von Neumann avec de la communication classique dans le cas de 3 personnes, mais la simulation des parties réelles résiste encore et toujours.

Quantum nonlocality, cryptography and complexity

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Network pricing problems : complexity, polyhedral study and solution approaches

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Une silhouette naturelle est-elle fréquemment classée dans plusieurs catégories de base?

Les silhouettes ambiguës, comme celle du lapin/canard (Jastrow, 1899), ont été étudiées selon plusieurs approches. Toutefois, les figures prises en exemples dans la large majorité des études sont généralement les mêmes. Cette redondance des images ambiguës utilisées pousse à croire qu'elles sont peut-être assez rares. Certaines observations anecdotiques suggèrent cependant qu’elles seraient au contraire relativement fréquentes. C'est ce que cherche à déterminer cette expérience. Nous avons utilisé des modèles tridimensionnels d'animaux projetés de façon aléatoire afin d'en extraire les silhouettes dont la complexité périmétrique a ensuite été modifiée par lissage. Treize sujets ont dû indiquer ce qu'ils percevaient dans l'image. Nous démontrons qu’une silhouette est classée en moyenne dans 1.9079 catégories de base. Nous avons également démontré qu’une diminution de la complexité périmétrique rend d’abord une silhouette plus ambiguë pour éventuellement atteindre un sommet (équivalent à environ six fois la complexité périmétrique d’un disque) à la suite duquel l’ambiguïté chute.