The topic of this thesis belongs to the theory of integer partitions, at the intersection of combinatorics and number theory. In particular, we study Rogers-Ramanujan type identities in the framework of the method of weighted words. This method revisited allows us to introduce new combinatorial objects beyond the classical notion of integer partitions: the generalized colored partitions. Using these combinatorial objects, we establish new Rogers-Ramanujan identities via two different approaches. The first approach consists of a combinatorial proof, essentially bijective, of the studied identities. This approach allowed us to establish some identities generalizing many important identities of the theory of integer partitions: Schur’s identity and Göllnitz’ identity, Glaisher’s identity generalizing Euler’s identity, the identities of Siladi´c, of Primc and of Capparelli coming from the representation theory of affine Lie algebras. The second approach uses the theory of perfect crystals, coming from the representation theory of affine Lie algebras. We view the characters of standard representations as some identities on the generalized colored partitions. In particular, this approach allows us to establish simple formulas for the characters of all the level one standard representations of type A_{n-1}^{(1)},A_{2n}^{(2)},D_{n+1}^{(2)},A_{2n-1}^{(2)},B_{n}^{(1)},D_{n}^{(1)}.

Most classical problems of communication complexity are Boolean functions. When considering functions of larger output, the way in which the result of a computation must be made available – the output model – can greatly impact the complexity of the problem. In particular, some lower bounds may not apply to all models. In this thesis, we study some lower bounds affected by the output model, problems with large outputs, revisit several classical results in the light of these output mechanisms, and relate them to the formalism of behaviors and Bell inequalities of quantum nonlocality.

Cette thèse présente de nouveaux algorithmes quantiques pour l'apprentissage automatique. L'ordinateur quantique permet un nouveau paradigme de calcul qui exploite les lois de la mécanique quantique pour offrir une accélération des calculs par rapport aux ordinateurs classiques.Dans cette thèse, je propose des algorithmes quantiques pour l'apprentissage de certains modèles d'apprentissage classique. Les nouveaux algorithmes quantiques développés ont été implémentés et simulés sur des ordinateurs classiques à base d’HPC, avec les jeux de donnés couramment utilisés pour l’apprentissage automatique classique. Je démontre ainsi que ces algorithmes ont effectivement le potentiel de concourir contre les meilleurs algorithmes classiques pour l’analyse de donnés.

Throughout the last two decades, a type of trajectories has been found to be almost ubiquitous in biological searches: the Lévy Patterns. Such patterns are fractal, with searches happening in self-similar clusters. Their hallmark is that their step-lengths are distributed in a power-law with some exponent μ ∈ (1, 3). This discovery lead to two intriguing questions: first, do these patterns emerge from an internal mechanism of the searcher, or from the interaction with the environment? Second, and independently of the previous question: what do these searchers have in common? When can we expect to see a Lévy Pattern of exponent μ? And how much does the knowledge of μ inform on the biological situation? Towards answering this second question, I will present an analysis of the efficiency of Lévy Walks when detection is weak, and targets appear in various sizes. In particular, I show that the much-debated inverse-square Lévy Walk is uniquely efficient in this setting. Regarding the question of how animals can perform Lévy Patterns, it has been suggested that animals could approximate a Lévy distribution by having k different modes of movement, where k = 2, 3. I will provide tight bounds for the performances of such an algorithm, which show, in accordance with the literature, that having k = 3 modes may be sufficiently efficient in biological scenarios.

Opetopes are shapes (akin to globules, cubes, simplices, dendrices, etc.) introduced by Baez and Dolan to describe laws and coherence cells in higher-dimensional categories. In a nutshell, they are trees of trees of trees of trees of… These shapes are attractive because of their simple nature and easy to find “in nature”, but their highly inductive definition makes them difficult to manipulate efficiently.
This thesis develops the theory of opetopes along three main axes. First, we give it clean and robust foundations by carefully detailing the approach of Kock et. al., based on polynomial monads and trees. Then, with the aim of computerized manipulation in mind, we introduce two syntactical approaches to opetopes and opetopic sets. In each, opetopes are represented as syntactical constructs whose well-formation conditions are enforced by corresponding sequent calculi. Lastly, we focus on the algebraic structures that can naturally be described by opetopes. So-called opetopic algebras include categories, planar operads, and Loday's combinads over planar trees. We show how classical results of Rezk, Joyal and Tierney (for ∞-categories), and Cisinski and Moerdijk (for ∞-operads) can be reformulated and generalized in the opetopic setting.

Manuscript

Cette thèse s’intéresse aux cartes combinatoires, qui sont définies comme des plongements de graphes sur des surfaces, ou de manière équivalente comme des recollements de polygones. Le genre g de la carte est défini comme le nombre d’anses que possède la surface sur laquelle elle est plongée. En plus d’être des objets combinatoires, les cartes peuvent être représentées comme des factorisations de permutations, ce qui en fait également des objets algébriques, qu’on peut notamment étudier grâce à la théorie des représentations du groupe symétrique. En particulier, ces propriétés algébriques des cartes font que leur série génératrice satisfait la hiérarchie KP( et sa généralisation, la hiérarchie 2-Toda). La hiérarchie KP est un ensemble infini d’équations aux dérivées partielles en une infinité de variables. Les équations aux dérivées partielles de la hiérarchie KP se traduisent ensuite en formules de récurrence qui permettent d’énumérer les cartes en tout genre. D’autre part, il est intéressant d’étudier les propriétés géométriques des cartes, et en particulier des très grandes cartes aléatoires. De nombreux travaux ont permis d’étudier les propriétés géométriques des cartes planaires, c’est à dire de genre 0. Dans cette thèse, on étudie les cartes de grand genre, c’est à dire dont le genre tend vers l’infini en même temps que la taille de la carte. Ce qui nous intéressera particulièrement est la notion de limite locale, qui décrit la loi du voisinage d’un point particulier (la racine) des grandes cartes aléatoires uniformes. La première partie de cette thèse est une introduction à toutes les notions nécessaires : les cartes, bien entendu, mais également la hiérarchie KP et les limites locales. Dans un deuxième temps, on cherchera à approfondir la relation entre cartes et hiérarchie KP, soit en expliquant des formules existantes par des constructions combinatoires, soit en découvrant de nouvelles formules. La troisième partie se concentre sur l’étude des limites locales des cartes de grand genre, en s’aidant notamment de résultats obtenus grâce à la hiérarchie KP. Enfin, on conclut par quelques problèmes ouverts.

Manuscrit

This thesis explores the benefits of non-laziness in both Implicit Computational Complexity and probabilistic computation. More specifically, this thesis can be divided in two main parts. In the first one, we investigate in all directions the mechanisms of linear erasure and duplication, which lead us to the type assignment systems LEM (Linearly Exponential Multiplicative Type Assignment) and LAM (Linearly Additive Multiplicative Type Assignment). The former is able to express weaker versions of the exponential rules of Linear Logic, while the latter has weaker additive rules, called linear additives. These systems enjoy, respectively, a cubic cut-elimination and a linear normalization result. Since linear additives do not require a lazy evaluation to avoid the exponential blow up in normalization (unlike the standard additives), they can be employed to obtain an implicit characterization of the functions computable in probabilistic polynomial time that does not depend on the choice of the reduction strategy. This result is achieved in STA⊕, a system that extends STA (Soft Type Assignment) with a randomized formulation of linear additives. Also, this system is able to capture the complexity classes PP and BPP. The second part of the thesis is focused on the probabilistic λ-calculus endowed with an operational semantics based on the head reduction, i.e. a non-lazy call-by-name evaluation policy. We prove that probabilistic applicative bisimilarity is fully abstract with respect to context equivalence. This result witnesses the discriminating power of non-laziness, which allows to recover a perfect match between the two equivalences that was missing in the lazy setting. Moreover, we show that probabilistic applicative similarity is sound but not complete for the context preorder.