Academic literature on the topic 'Complexité de circuits'

La complexité arithmétique est l'étude des ressources nécessaires pour calcu- ler des polynômes en n'utilisant que des opérations arithmétiques. À la fin des années 70, Valiant a défini (de manière semblable à la complexité booléenne) des classes de polynômes. Les polynômes, ayant des circuits de taille polyno- miale, considérés faciles forment la classe VP. Les sommes exponentielles de ces derniers correpondent alors à la classe VNP. L'hypothèse de Valiant est la conjecture que VP ̸= VNP.Bien que cette conjecture soit encore grandement ouverture, cette dernière semble toutefois plus accessible que son homologue booléen. La structure algé- brique sous-jacente limite les possibilités de calculs. En particulier, un résultat important du domaine assure que les polynômes faciles peuvent aussi être cal- culés efficacement en paralèlle. De plus, quitte à autoriser une augmentation raisonnable de la taille, il est possible de les calculer avec une profondeur de calcul bornée par une constante. Comme ce dernier modèle est très restreint, de nombreuses bornes inférieures sont connues. Nous nous intéresserons en premier temps à ces résultats sur les circuits de profondeur constante.Bürgisser a montré qu'une conjecture (la τ-conjecture) qui borne supérieu- rement le nombre de racines de certains polynômes univariés, impliquait des bornes inférieures en complexité arithmétique. Mais, que se passe-t-il alors, si on essaye de réduire, comme précédemment, la profondeur du polynôme consi- déré? Borner le nombre de racines réelles de certaines familles de polynômes permetterait de séparer VP et VNP. Nous étudierons finalement ces bornes su- périeures sur le nombre de racines réelles.

This research in Theoretical Computer Science extends the gateways between Linear Logic and Complexity Theory by introducing two innovative models of computation. It focuses on sub-polynomial classes of complexity : AC and NC —the classes of efficiently parallelizable problems— and L and NL —the deterministic and non-deterministic classes of problems efficiently solvable with low resources on space. Linear Logic is used through its Proof Net resentation to mimic with efficiency the parallel computation of Boolean Circuits, including but not restricted to their constant-depth variants. In a second moment, we investigate how operators on a von Neumann algebra can be used to model computation, thanks to the method provided by the Geometry of Interaction, a subtle reconstruction of Linear Logic. This characterization of computation in logarithmic space with matrices can naturally be understood as a wander on simple structures using pointers, parsing them without modifying them. We make this intuition formal by introducing Non Deterministic Pointer Machines and relating them to other well-known pointer-like-machines. We obtain by doing so new implicit characterizations of sub-polynomial classes of complexity<br>Cette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables (NC et AC) et celle des problèmes solutionnables avec peu d’espace, dans ses versions déterministes et non-déterministes (L et NL). La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s’inspire de la géométrie de l’interaction, une délicate reconstruction de la logique linéaire à l’aide d’opérateurs d’une algèbre de von Neumann. Nous détaillons comment l’interaction d’opérateurs représentant des entiers et d’opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d’autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial

Au cours de la thèse, nous nous sommes intéressés aux problèmes d'empilement de wafers. Ces problèmes apparaissent lors de la fabrication de processeurs en 3 dimensions. Au cours du processus de fabrication, les puces électroniques doivent être empilées les unes sur les autres. Jusqu'à peu, ces dernières, une fois gravées sur des plaques de silicium appelées wafers, étaient découpées, puis triées afin d'écarter les puces défectueuses et enfin assemblées les unes entre elles.Cependant empiler les wafers plutôt que les puces présente de nombreux avantages techniques et financiers. Naturellement, étant impossible d'écarter les puces défectueuses sans découper la plaque de silice, le problème de la superposition d'une puce viable avec une puce défectueuse se pose. Une pile de puces, étant considérées comme défectueuse si elle contient ne serait-ce qu'une puce défectueuse, la superposition non réfléchie des wafers entre eux mènerait à un rendement désastreux.Afin de générer un nombre minimum de piles défectueuses, une "cartographie" de chaque wafer candidat à la superposition est réalisée lors d'une phase de test, permettant de situer les puces défectueuses sur le wafer. Une fois cette cartographie réalisée, l'objectif est de sélectionner les wafers qui seront assemblés ensembles de manière à faire correspondre les défauts de chacun des wafers.Ce problème peut être modélisé à l'aide d'un problème d'affectation multidimensionnelle. Chaque wafer est représenté par un vecteur comportant autant de composantes que de puces sur le wafer qu'il représente. Une composante égale à zéro matérialise une puce défectueuse tandis qu'un un matérialise une puce viable. Chaque lot de wafers est représenté par un lot de vecteurs. Formellement, une instance d'empilement de wafers est représenté par m ensembles de n vecteurs binaires p-dimensionnels. L'objectif est alors de réaliser n m-uplets disjoints contenant exactement un vecteur par ensemble. Ces m-uplets représenteront les piles. Chaque m-uplet peut être représenté par un vecteur binaire p-dimensionnels, chaque composante étant calculée en réalisant le ET binaire des composantes correspondantes des vecteurs qui composent le m-uplet. Autrement dit, une composante du vecteur représentant le m-uplet est égale à un si et seulement si tous les vecteurs ont cette composante égale à un. Et donc une pile de puces est viables si toutes les puces qui la composent sont viables. L'objectif est alors de minimiser le nombre de zéros ou de maximiser le nombre de un.La thèse comporte deux grandes parties. Une partie théorique abordant la complexité des différentes versions du problèmes en fonction de certains paramètres tels que m, n, p ou encore le nombre maximum de zéros par vecteurs. Nous montrons entre autre que ces problèmes peuvent être utilisés pour modéliser des problèmes plus classiques tels que Maximum Clique, Minimum Vertex Cover ou encore k-Dimensional Matching, permettant de prouver un certain nombre de résultats négatifs que ce soit d'un point de vue de la complexité classique, l'approximabilité ou la complexité paramétrée. Nous fournissons également des résultats positifs pour des cas particuliers du problème.Dans un second temps, nous nous intéressons à la résolution pratique du problème en fournissant et comparant un certain nombre de formulations en Programmation Linéaire en Nombres Entiers. Mais nous nous intéressons également aux performances en pratique de certaines heuristiques à garantie de performances détaillées dans la partie théorique<br>In this thesis, we focused in the Wafer-to-Wafer integration problems. These problems come from IC manufacturing. During the production of three-dimensional processors, dies have to be superimposed. Until recent, the dies were engraved on a silicon disk called wafer, then were cut, tested and sorted to suppress faulty dies and lastly superimposed one to each other.However superimposing wafers instead of dies presents several technical and financial advantages. Since faulty dies can only be dismissed when cutting the wafer, superimpose two wafers can lead to superimpose a faulty die with a viable one. In this case, the resulting stack of dies is considered as faulty. It follows that a bad assignment between the wafers can lead to a disastrous yield.In order to minimize the number of faulty dies stacks, a "failure map" of each wafer is generated during a test phase. This map gives location of the faulty dies on the wafers. The objective is then to take advantage of this map to define an assignment of the wafers to each other in order to match as many failures as possible.This problem can be modelized with Multidimensional Assignment problems. Each wafer can be seen as a vector with as many dimensions as the number of dies engraved on it. A coordinate set to zero marks a faulty die while a coordinate set to one indicates a viable one. Each seat of wafers is represented by a set of vector. Formally, an instance of a Wafer-to-Wafer integration problem is represented by m sets of n p-dimensional vectors. The objective is then to partition the vectors into n disjoint m-tuples, each tuple containing exactly one vector per set. An m-tuple represents a stack of wafers. Every m-tuple can be represented by a p-dimensional vector. Each coordinate is computed by performing the bitwise AND between the corresponding coordinates of the vectors that compose the m-tuple. In other words, a coordinate of the representative vector is equal to one if and only if this coordinate is equal to one in every vector composing the tuple. It follows that a dies stack is viable if and only if all the dies composing the stack are viable. The objective is then to maximize the overall number of ones of to minimize the overall number of zeros.The first part of the thesis is a theoretical one. We study the complexity of the considered versions of the problem with regards to natural parameters such as m, n, p or the number of zeros per vector. We show that these problems can encode more classical problems such as Maximum Clique, Minimum Vertex Cover or k-Dimensional Matching. This leads to several negative results from computational complexity, approximability or even parameterized complexity point of view. We also provide several positive results for some specific cases of the problem.In a second part, we focus on the practical solving of the problem. We provide and compare several Integer Linear Programming formulations. We also focus on performances of some approximation algorithms that we detailed in the theoretical part

Le cadre de la these est celui de la synthese d'architectures, ce dernier regroupe l'ensemble des techniques mises en uvre pour concevoir de maniere automatique et optimisee des circuits realisant des applications decrites simplement de maniere comportementale. Dans ce domaine est aborde specifiquement le probleme de l'estimation a priori du cout d'une architecture, sous contrainte de temps d'iteration. Deux methodes nouvelles sont presentees, chacune repondant a un objectif different. La premiere est une estimation probabiliste et dynamique, elle fournit au concepteur des metriques lui permettant de juger de la complexite materielle et de la repartition des ressources dans le temps. Son but est de caracteriser les choix de specifications effectues, de maniere a favoriser par la suite le recours a d'eventuelles transformations de types algorithmique, fonctionnel et structurel. Il s'agit d'une etude faisant appel a une notion recente et peu etudiee, celle du guidage dans l'espace des transformations pour l'optimisation de l'adequation algorithme architecture. La seconde technique proposee est consacree a l'estimation precise des ressources materielles requises par l'algorithem traite, pour respecter la contrainte de temps. Elle s'adresse a l'utilisateur et a l'outil de cao. Son originalite provient du calcul dual des besoins en unites fonctionnelles et du pipeline associe, a travers une etude fine des causes de sous et sur-estimation. De cette estimation, ressort egalement une connaissance precise de la mobilite exacte des operations du graphe flot de donnees sans a priori sur l'ordonnancement. Les deux types d'estimations sont integrees dans l'outil de synthese d'architecture gaut

Cette thèse explore deux territoires distincts de l’informatique fondamentale : la complexité et la compression. Plus précisément, dans une première partie, nous étudions la puissance des circuits arithmétiques non commutatifs, qui calculent des polynômes non commutatifs en plusieurs indéterminées. Pour cela, nous introduisons plusieurs modèles de calcul, restreints dans leur manière de calculer les monômes. Ces modèles en généralisent d’autres, plus anciens et largement étudiés, comme les programmes à branchements. Les résultats sont de trois sortes. Premièrement, nous donnons des bornes inférieures sur le nombre d’opérations arithmétiques nécessaires au calcul de certains polynômes tels que le déterminant ou encore le permanent. Deuxièmement, nous concevons des algorithmes déterministes fonctionnant en temps polynomial pour résoudre le problème du test d’identité polynomiale. Enfin, nous construisons un pont entre la théorie des automates et les circuits arithmétiques non commutatifs, ce qui nous permet de dériver de nouvelles bornes inférieures en utilisant une mesure reposant sur le rang de la matrice dite de Hankel, provenant de la théorie des automates. Une deuxième partie concerne l’analyse de l’algorithme de compression sans perte Lempel-Ziv. Pourtant très utilisé, sa stabilité est encore mal établie. Vers la fin des années 90s, Jack Lutz popularise la question suivante, connue sous le nom de « one-bit catastrophe » : « étant donné un mot compressible, est-il possible de le rendre incompressible en ne changeant qu’un seul bit ? ». Nous montrons qu’une telle catastrophe est en effet possible. Plus précisément, en donnant des bornes optimales sur la variation de la taille de la compression, nous montrons qu’un mot « très compressible » restera toujours compressible après modification d’un bit, mais que certains mots « peu compressibles » deviennent en effet incompressibles<br>This thesis explores two territories of computer science: complexity and compression. More precisely, in a first part, we investigate the power of non-commutative arithmetic circuits, which compute multivariate non-commutative polynomials. For that, we introduce various models of computation that are restricted in the way they are allowed to compute monomials. These models generalize previous ones that have been widely studied, such as algebraic branching programs. The results are of three different types. First, we give strong lower bounds on the number of arithmetic operations needed to compute some polynomials such as the determinant or the permanent. Second, we design some deterministic polynomial-time algorithm to solve the white-box polynomial identity problem. Third, we exhibit a link between automata theory and non-commutative arithmetic circuits that allows us to derive some old and new tight lower bounds for some classes of non-commutative circuits, using a measure based on the rank of a so-called Hankel matrix. A second part is concerned with the analysis of the data compression algorithm called Lempel-Ziv. Although this algorithm is widely used in practice, we know little about its stability. Our main result is to show that an infinite word compressible by LZ’78 can become incompressible by adding a single bit in front of it, thus closing a question proposed by Jack Lutz in the late 90s under the name “one-bit catastrophe”. We also give tight bounds on the maximal possible variation between the compression ratio of a finite word and its perturbation—when one bit is added in front of it

La conjecture de Straubing, énoncée dans son livre publié en 1994, suggère qu'un langage régulier définissable par un fragment logique équipé d'une signature arbitraire, est définissable par le même fragment logique mais équipé d'une signature régulière. Les fragments logiques considérés sont des classes de férmules de la logique monadique du second ordre sur les mots finis. Cette thèse est une contribution à l'étude de le conjecture de Straubing. Pour prouver une telle conjecture, il semble nécessaire pour établir cette conjecture de prouver deux résultats de natures différentes : 1. Des caractérisations algébriques de classes de langages réguliers définies par des fragments logiques équipés de prédicats réguliers, 2. Des résultats de non-définissabilité de langages réguliers dans des fragments logiques équipés de prédicats numériques arbitraires. La première partie de cette thèse est dédiée à l'ajout des prédicats réguliers à un fragment logique et en particulier, celui des prédicats modulaires lorsque les fragments logiques disposent de structures algébriques. La seconde partie de cette thèse est dédiée à des résultats de non définissablité, et en particulier l'étude du fragment à deux variables de la logique du premier ordre<br>The Straubing conjecture, stated in his book published in 1994, suggest that a regular language definable by a fragment of logic and equipped with an arbitrary numerical signature is definable using the same fragment of logic using only regular predicates. The considered fragments of logic are classed of formulas of monadic second order logic over finite words. This thesis is a contribution to the study of the Straubing conjecture. To prove such a conjecture, it seems necessary to obtain two results of two distinct types: 1. Algebraic characterizations of classes of regular languages defined by fragments of logics equipped with regular predicates, 2. Undefinability results of regular languages in fragments of logics equipped with arbitrary numerical predicates. The first part of this thesis is dedicated to the operation of adding regular predicates to a given fragment of logic, with a particular focus on modular predicates in the case where logical fragments have some algebraic structure. The second par of this thesis is dedicated to undefinability results with a particular focus on two-variable first order logic

Ce memoire concerne l'etude et le developpement de techniques d'analyse de testabilite de descriptions comportementales de circuits. Ces techniques ont pour objectif de reduire le cout du processus de generation de sequences de test comportemental. Ce cout etant directement lie a la complexite des descriptions comportementales et a la complexite de la strategie de generation des sequences de test comportemental, les techniques presentees ont ete adaptees des domaines du test du logiciel et du test du materiel. Elles ont ete developpees au sein d'un environnement de testabilite comportementale nomme betie. Ce dernier contient les trois outils suivants: un outil de mesure de complexite de descriptions comportementales, un outil d'identification de fragments de descriptions a ameliorer et un outil de mesure de testabilite de descriptions comportementales

The intended goal of this manuscript is to build bridges between two definitions of complexity. One of them, called the algorithmic complexity is well-known to any computer scientist as the difficulty of performing some task such as sorting or optimizing the outcome of some system. The other one, etymologically closer from the word "complexity" is about what happens when many parts of a system are interacting together. Just as cells in a living body, producers and consumers in some non-planned economies or mathematicians exchanging ideas to prove theorems. On the algorithmic side, the main objects that we are going to use are two models of computations, one called communication protocols, and the other one circuits. Communication protocols are found everywhere in our world, they are the basic stone of almost any human collaboration and achievement. The definition we are going to use of communication reflects exactly this idea of collaboration. Our other model, circuits, are basically combinations of logical gates put together with electrical wires carrying binary values, They are ubiquitous in our everyday life, they are how computers compute, how cell phones make calls, yet the most basic questions about them remain widely open, how to build the most efficient circuits computing a given function, How to prove that some function does not have a circuit of a given size, For all but the most basic computations, the question of whether they can be computed by a very small circuit is still open. On the other hand, our main object of study, cellular automata, is a prototype of our second definition of complexity. What "does" a cellular automaton is exactly this definition, making simple agents evolve with interaction with a small neighborhood. The theory of cellular automata is related to other fields of mathematics, such as dynamical systems, symbolic dynamics, and topology. Several uses of cellular automata have been suggested, ranging from the simple application of them as a model of other biological or physical phenomena, to the more general study in the theory of computation.

Cette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables (NC et AC) et celle des problèmes solutionnables avec peu d'espace, dans ses versions déterministes et non-déterministes (L et NL). La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s'inspire de la géométrie de l'interaction, une délicate reconstruction de la logique linéaire à l'aide d'opérateurs d'une algèbre de von Neumann. Nous détaillons comment l'interaction d'opérateurs représentant des entiers et d'opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d'autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial.