Probabilistic graphical models have been successfully applied to a wide variety of fields such as computer vision, natural language processing, robotics, and many more. However, for large scale problems represented using unrestricted probabilistic graphical models, exact inference is often intractable, which means that the model cannot compute the correct value of a joint probability query in a reasonable time. In general, approximate inference has been used to address this intractability, in which the exact joint probability is approximated. An increasingly popular alternative is tractable models. These models are constrained such that exact inference is efficient. To offer efficient exact inference, tractable models either benefit from graph-theoretic properties, such as bounded treewidth, or structural properties such as local structures, determinism, or symmetry. An appealing group of probabilistic models that capture local structures and determinism includes arithmetic circuits (ACs) and sum-product networks (SPNs), in which marginal and conditional queries can be answered efficiently. In this dissertation, we describe ID-SPN, a state-of-the-art SPN learner as well as novel methods for learning tractable graphical models in a discriminative setting, in particular through introducing Generalized ACs, which combines ACs and neural networks. Using extensive experiments, we show that the proposed methods often achieves better performance comparing to selected baselines. This dissertation includes previously published and unpublished co-authored material. / 10000-01-01

The increasing capabilities of multimedia appliances demand arithmetic circuits with higher speed and reasonable power dissipation. A common technique to attain those goals is synchronous pipelining, which increases the throughput of a circuit at the expense of longer latency, and it is therefore suitable where throughput takes priority over latency. Two synchronous pipelining approaches, conventional pipelining and wave pipelining, are commonly employed. Conventional pipelining uses registers to divide the circuit into shorter paths and synchronize among sub-blocks, while wave pipelining uses the delay of combinational elements to perform those tasks. As wave pipelining does not introduce additional registers, in principle, it can attain a higher throughput and lower power consumption. However, its throughput is limited by delay variations, while delay balancing often leads to increased power dissipation. This dissertation proposes a hybrid pipelining method called HyPipe, which divides the circuit into sub-blocks using conventional pipelining, and applies wave pipelining to each sub-block. Each sub-block is derived from a single base circuit, leading to a better delay balance and greater throughput than with heterogeneous circuits. Another requirement for wave pipelining to achieve high speed is short signal rise and fall times. Since CMOS wide-NAND and wide-NOR gates exhibit long rise and fall times and large delay variations, they should be decomposed. We show that the straightforward decomposition using alternating levels of NAND and NOR gates results in large delay variations. Therefore, we propose a new decomposition method using only one gate type. Our method reduces delay variations by up to 39%, and it is appropriate for wave pipelining based on standard-cells or sea-of-gates. We laid out a 4x4 HyPipe multiplier as a proof of concept and performed a post-layout SPICE simulation. The multiplier achieves a throughput of 4.17 billion multiplications per second or a clock period of 2.52 four-load inverter delays, which is almost twice the speed of any existing multiplier in the open literature. When the supply voltage is reduced to 1.2 V from 1.8 V, its power consumption is reduced from 76.2 mW to 18.2 mW while performing 2.33 billion multiplications per second. / Ph. D.

We study the problem of proving lower bounds for depth four arithmetic circuits. Depth four circuits have been receiving much attraction when it comes to recent circuit lower bound results, as a result of the series of results culminating in the fact that strong enough lower bounds for depth four circuits will imply super-polynomial lower bounds for general arithmetic circuits, and hence solve one of the most central open problems in algebraic complexity i.e a separation between the VP and VNP classes. However despite several efforts, even for general arithmetic circuits, the best known lower bound is Omega(N log N) by Baur and Strassen (1983), where N is the number of input variables. In the case of arithmetic formulas, Kalorkoti (1985) proved a lower bound that is quadratic in the number of input variables, which has not seen any improvement since then. The situation for depth three arithmetic circuits was also similar for many years, until a recent result by Kayal et. al. (2016) achieved an almost cubic lower bound that improved over the previous best quadratic bound by Shpilka and Wigderson (1999). As the main contribution of this thesis, we prove an Omega(N^1.5) lower bound on the size of a depth four circuit, for an explicit multilinear N-variate polynomial in VNP with degree d = Theta(sqrt(N)). Our approach offers a potential route to proving a super-quadratic lower bound for depth four circuits. Taking cue from the numerous successful results recently, we use the technique of the shifted partial derivatives measure to achieve the said lower bound. Particularly, we use the Dimension of Projected Shifted Partials (DPSP) measure which has been previously used in recent depth four results. Coming to the choice of the hard polynomial, we again follow the status quo and use a variant of the Nisan-Wigderson (NW) polynomial family that has proved to be very helpful over the past few years in arithmetic circuit complexity. Finally, we do a careful analysis of Shoup-Smolensky (1997) and Raz (2010) and compare their techniques to ours. We conclude that our result can potentially be used as a starting point, and techniques similar to Kayal et. al. (2016) can likely be used to strengthen our lower bound to Omega(N^2.5), for general depth four arithmetic circuits. However, unlike depth three circuits, proving a super-quadratic lower bound for depth four circuits remains a prevalent open problem for many years. Previous work like Shoup-Smolensky and Raz implied super-linear lower bounds. To the best of our knowledge, the previous best known lower bound for general depth four circuits is Omega(N^1.33).

É contínua a procura por técnicas de construção de circuitos que ajudem a minimizar os problemas existentes no mercado de microeletrônica atual. Uma alternativa para a resolução destes problemas consiste na utilização de circuitos assíncronos. Circuitos aritméticos são alvo de um contínuo esforço na busca de melhores resultados de desempenho e área. Em especial o somador é uma das partes constituintes desta classe de circuitos que apresenta interessante campo para pesquisas. Este trabalho apresenta um método de avaliação de somadores implementados através do uso de famílias lógicas CMOS dual-rail. Esta tarefa é realizada através do uso de um circuito assíncrono que serve como base de avaliação. Este circuito obedece ao protocolo de comunicação utilizado pelos somadores e nele são desenvolvidas diversas aplicações para que seja possível avaliar o comportamento dos somadores quando expostos a diferentes padrões de vetores. Os parâmetros avaliados nas estruturas dos somadores são número de transistores, atraso e consumo de potência para topologias carry look-ahead e ripple carry adders. Na avaliação dos somadores através de simulação elétrica são utilizadas as ferramentas Pspice e Spectre da Cadence. As tecnologias utilizadas nesta caracterização são AMI 0.5 da MOSIS e AMS 0.35. Como resultados são apresentados dados que demonstram a economia no número de transistores obtida através do uso da técnica de múltiplas saídas para o CLA, que a família DCVS geralmente apresenta os menores atrasos médios quando comparada a outras estruturas e a potencialidade de famílias NCL. / The search for construction techniques of circuits that helps to minimize the challenges that occurs in nowadays microelectronic market is continuous. An alternative to solve great part of these problems is the use of asynchronous circuits. Arithmetic circuits are the target of a continuous effort in the pursuit of better results in terms of performance and area. Adder circuits in special compose a subset of this class of circuits that presents an interesting research field. This work presents an evaluation method for adders that where implemented through different dual-rail logic families. This task is accomplished through the use of asynchronous circuits used as an evaluation base. The asynchronous circuits implemented obey the communication protocol adopted by the adders and implement different applications. These applications are constructed with the finality of study the adder’s behavior when they are exposed to different vector patterns. The adder’s evaluated parameters are the number of transistors, delay and power consumption of topologies like Carry Look-ahead and Ripple Carry Adders. The electrical simulations were accomplished trough the use of Pspice and Cadence’s Spectre cad tools. MOSIS AMI 0.5 and AMS 0.35 transistor technologies were utilized in the electrical characterization of the adders. Some of the results obtained trough this work that could be cited are: the low transistor count presented for the Multiple Outputs CLA structures, the performance advantage of the DCVS family in relation to the other families and the evaluation of NCL logic family potentiality.

É contínua a procura por técnicas de construção de circuitos que ajudem a minimizar os problemas existentes no mercado de microeletrônica atual. Uma alternativa para a resolução destes problemas consiste na utilização de circuitos assíncronos. Circuitos aritméticos são alvo de um contínuo esforço na busca de melhores resultados de desempenho e área. Em especial o somador é uma das partes constituintes desta classe de circuitos que apresenta interessante campo para pesquisas. Este trabalho apresenta um método de avaliação de somadores implementados através do uso de famílias lógicas CMOS dual-rail. Esta tarefa é realizada através do uso de um circuito assíncrono que serve como base de avaliação. Este circuito obedece ao protocolo de comunicação utilizado pelos somadores e nele são desenvolvidas diversas aplicações para que seja possível avaliar o comportamento dos somadores quando expostos a diferentes padrões de vetores. Os parâmetros avaliados nas estruturas dos somadores são número de transistores, atraso e consumo de potência para topologias carry look-ahead e ripple carry adders. Na avaliação dos somadores através de simulação elétrica são utilizadas as ferramentas Pspice e Spectre da Cadence. As tecnologias utilizadas nesta caracterização são AMI 0.5 da MOSIS e AMS 0.35. Como resultados são apresentados dados que demonstram a economia no número de transistores obtida através do uso da técnica de múltiplas saídas para o CLA, que a família DCVS geralmente apresenta os menores atrasos médios quando comparada a outras estruturas e a potencialidade de famílias NCL. / The search for construction techniques of circuits that helps to minimize the challenges that occurs in nowadays microelectronic market is continuous. An alternative to solve great part of these problems is the use of asynchronous circuits. Arithmetic circuits are the target of a continuous effort in the pursuit of better results in terms of performance and area. Adder circuits in special compose a subset of this class of circuits that presents an interesting research field. This work presents an evaluation method for adders that where implemented through different dual-rail logic families. This task is accomplished through the use of asynchronous circuits used as an evaluation base. The asynchronous circuits implemented obey the communication protocol adopted by the adders and implement different applications. These applications are constructed with the finality of study the adder’s behavior when they are exposed to different vector patterns. The adder’s evaluated parameters are the number of transistors, delay and power consumption of topologies like Carry Look-ahead and Ripple Carry Adders. The electrical simulations were accomplished trough the use of Pspice and Cadence’s Spectre cad tools. MOSIS AMI 0.5 and AMS 0.35 transistor technologies were utilized in the electrical characterization of the adders. Some of the results obtained trough this work that could be cited are: the low transistor count presented for the Multiple Outputs CLA structures, the performance advantage of the DCVS family in relation to the other families and the evaluation of NCL logic family potentiality.

É contínua a procura por técnicas de construção de circuitos que ajudem a minimizar os problemas existentes no mercado de microeletrônica atual. Uma alternativa para a resolução destes problemas consiste na utilização de circuitos assíncronos. Circuitos aritméticos são alvo de um contínuo esforço na busca de melhores resultados de desempenho e área. Em especial o somador é uma das partes constituintes desta classe de circuitos que apresenta interessante campo para pesquisas. Este trabalho apresenta um método de avaliação de somadores implementados através do uso de famílias lógicas CMOS dual-rail. Esta tarefa é realizada através do uso de um circuito assíncrono que serve como base de avaliação. Este circuito obedece ao protocolo de comunicação utilizado pelos somadores e nele são desenvolvidas diversas aplicações para que seja possível avaliar o comportamento dos somadores quando expostos a diferentes padrões de vetores. Os parâmetros avaliados nas estruturas dos somadores são número de transistores, atraso e consumo de potência para topologias carry look-ahead e ripple carry adders. Na avaliação dos somadores através de simulação elétrica são utilizadas as ferramentas Pspice e Spectre da Cadence. As tecnologias utilizadas nesta caracterização são AMI 0.5 da MOSIS e AMS 0.35. Como resultados são apresentados dados que demonstram a economia no número de transistores obtida através do uso da técnica de múltiplas saídas para o CLA, que a família DCVS geralmente apresenta os menores atrasos médios quando comparada a outras estruturas e a potencialidade de famílias NCL. / The search for construction techniques of circuits that helps to minimize the challenges that occurs in nowadays microelectronic market is continuous. An alternative to solve great part of these problems is the use of asynchronous circuits. Arithmetic circuits are the target of a continuous effort in the pursuit of better results in terms of performance and area. Adder circuits in special compose a subset of this class of circuits that presents an interesting research field. This work presents an evaluation method for adders that where implemented through different dual-rail logic families. This task is accomplished through the use of asynchronous circuits used as an evaluation base. The asynchronous circuits implemented obey the communication protocol adopted by the adders and implement different applications. These applications are constructed with the finality of study the adder’s behavior when they are exposed to different vector patterns. The adder’s evaluated parameters are the number of transistors, delay and power consumption of topologies like Carry Look-ahead and Ripple Carry Adders. The electrical simulations were accomplished trough the use of Pspice and Cadence’s Spectre cad tools. MOSIS AMI 0.5 and AMS 0.35 transistor technologies were utilized in the electrical characterization of the adders. Some of the results obtained trough this work that could be cited are: the low transistor count presented for the Multiple Outputs CLA structures, the performance advantage of the DCVS family in relation to the other families and the evaluation of NCL logic family potentiality.

This thesis describes an efficient method for speeding up functional verification of arithmetic circuits namely linear network such as wallace trees, counters using linear algebra techniques. The circuit is represented as a network of half adders, full adders and inverters, and modeled as a system of linear equations. The proof of functional correctness of the design is obtained by computing its algebraic signature using standard linear programming (LP) solver and comparing it with the reference signature provided by the designer. Initial experimental results and comparison with Satisfiability Modulo Theorem (SMT) solvers show that the method is efficient, scalable and applicable to complex arithmetic designs, including large multipliers. It is intended to provide a new front end theory/engine to enhance SMT solvers.

Στα σύγχρονα ψηφιακά συστήματα η ανάγκη για γρήγορους υπολογισμούς είναι πλέον από τους πιο καθοριστικούς παράγοντες. Άλλοι ιδιαίτερα κρίσιμοι παράγοντες είναι η απαιτούμενη επιφάνεια του κυκλώματος και η κατανάλωση ενέργειας. Ωστόσο, ο χρόνος παραμένει ένας από τους πιο σημαντικούς για πλήθος εφαρμογές. Τα αριθμητικά κυκλώματα, όπως αθροιστές, πολλαπλασιαστές και κυκλώματα ύψωσης στο τετράγωνο, είναι πλέον αναπόσπαστο κομμάτι των ψηφιακών κυκλωμάτων, γι’ αυτό η επιτάχυνση των λειτουργιών αυτών είναι ένας στόχος στην κατεύθυνση του οποίου πολλές διαφορετικές αρχιτεκτονικές έχουν προταθεί. Η μείωση της καθυστέρησης στις αριθμητικές μονάδες θα δώσει μεγάλη βελτίωση στη συνολική απόδοση των συστημάτων, μιας και οι περισσότερες εφαρμογές εμπεριέχουν πλήθος αριθμητικών πράξεων. Η πράξη της ύψωσης στο τετράγωνο αποτελεί ειδική περίπτωση της πράξης του πολλαπλασιασμού, στην οποία ο πολλαπλασιαστέος ισούται με τον πολλαπλασιαστή. Ο λόγος για τον οποίο χρησιμοποιούμε εξειδικευμένα κυκλώματα για την πράξη αυτή είναι η εκμετάλλευση του γεγονότος ότι τα δύο έντελα είναι ίσα, κάτι που οδηγεί σε ελαχιστοποίηση του χρόνου που απαιτείται για την ολοκλήρωση της πράξης, αλλά και μείωση της απαιτούμενης επιφάνειας. Η πράξη της ύψωσης στο τετράγωνο χρησιμοποιείται σε πολλές εφαρμογές των υψηλής απόδοσης επεξεργαστών ψηφιακού σήματος (digital signal processors – DSP). Τέτοιες εφαρμογές συμπεριλαμβάνουν φιλτράρισμα σήματος (signal filtering), επεξεργασία εικόνας (image processing), και διαμόρφωση για τηλεπικοινωνιακά συστήματα. Η πράξη της ύψωσης στο τετράγωνο μπορεί, επίσης, να χρησιμοποιηθεί αποδοτικά στην υλοποίηση κρυπτογραφικών αλγορίθμων για την αποφυγή της χρονοβόρας διαδικασίας της ύψωσης σε δύναμη. Το Σύστημα Αριθμητικής Υπολοίπων (RNS), είναι ένα αριθμητικό σύστημα το οποίο παρουσιάζει σημαντικά πλεονεκτήματα στην ταχύτητα με την οποία μπορούν να γίνουν οι αριθμητικές πράξεις. Στο RNS οι αριθμοί αναπαρίστανται σαν ένα σύνολο από υπόλοιπα. Για να αναπαραστήσουμε έναν αριθμό ορίζουμε ένα σύνολο από πρώτους μεταξύ τους ακεραίους που ονομάζεται βάση του συστήματος P={p1,p2,…pk}. Η αναπαράσταση ενός αριθμού X στο RNS ορίζεται ως το σύνολο των υπολοίπων του Χ ως προς τα στοιχεία της βάσης Ρ. Προκύπτει, έτσι, ότι X={x1,x2,…,xk} όπου το xi είναι το υπόλοιπο της διαίρεσης του X με το στοιχείο της βάσης pi και συμβολίζεται με Xi=|X|pi. Κάθε ακέραιος Χ που ανήκει στο εύρος τιμών 0<=X<M, όπου Μ είναι το γινόμενο όλων των στοιχείων της βάσης P, έχει μοναδική αναπαράσταση στο RNS. Μια αριθμητική πράξη δύο εντέλων, η οποία μπορεί να είναι πρόσθεση, αφαίρεση ή πολλαπλασιασμός, ορίζεται ως εξής: {z1,z2,…,zk} = {x1,x2,…,xk}*{y1,y2,…,yk}, όπου zi = (xi*yi) modpi. Συνεπώς, κάθε αριθμητική πράξη εφαρμόζεται σε παράλληλες μονάδες (μία για κάθε στοιχείο της βάσης), καθεμία από τις οποίες διαχειρίζεται μικρούς αριθμούς (υπόλοιπα), αντί μιας μονάδας που θα χρειαζόταν να διαχειριστεί μεγάλους αριθμούς. Ένα από τα πιο δημοφιλή σύνολα βάσης είναι αυτά της μορφής {2^n, 2^n -1, 2^n+1}, λόγω του ότι προσφέρουν πολύ αποδοτικά κυκλώματα με κριτήριο το γινόμενο της επιφάνειας επί το τετράγωνο της καθυστέρησης (area * time^2), καθώς επίσης και αποδοτικούς μετατροπείς από και προς το δυαδικό σύστημα. Για το λόγο αυτό η υλοποίηση αποδοτικών modulo(2^n-1) και modulo(2n+1) κυκλωμάτων είναι σημαντική. Το πρόβλημα που παρουσιάζεται είναι ότι ενώ οι modulo(2^n) και modulo(2^n-1) αριθμητικές χρειάζονται το πολύ n δυαδικά ψηφία για την αναπαράσταση όλων των δυνατών υπολοίπων, στη modulo(2^n+1) αρχιτεκτονική χρειάζονται (n+1) ψηφία. Το πρόβλημα αυτό λύνεται με τη χρήση diminished-1 αναπαράστασης. Στη diminished-1 αναπαράσταση, κάθε αριθμός Χ αναπαρίσταται ως X-1=X-1. Έτσι, απαιτούνται n δυαδικά ψηφία για την αναπαράσταση, χρειάζονται, όμως, κυκλώματα μετατροπής από και προς την diminished-1 αναπαράσταση. Όταν χρησιμοποιείται η diminished-1 αναπαράσταση η τιμή εισόδου ίση με 0 χειρίζεται ξεχωριστά. Στα πλαίσια της εργασίας αναλύονται υπάρχουσες αρχιτεκτονικές και προτείνονται νέες για κυκλώματα ύψωσης στο τετράγωνο στο Σύστημα Αριθμητικής Υπολοίπων (RNS). Οι προτεινόμενες αρχιτεκτονικές βελτιώνουν την καθυστέρηση και, ταυτόχρονα, μειώνουν τις απαιτήσεις σε επιφάνεια. / Fast computations are of major importance in modern digital systems. Other critical factors are the area and the energy consumption. However, delay is still one of the most important ones for a variety of applications. Due to the fact that arithmetic circuits, such as adders, multipliers and squarers, have been integral components of most digital systems, many schemes have been proposed in the direction of accelerating arithmetic operations. As most applications contain a big number of arithmetic operations, delay reduction in arithmetic units will lead to significant improvement in the total system’s performance. Squaring is a special case of multiplication, where the multiplier equals the multiplicand. The reason for using a special circuit for squaring is to benefit from the fact that the two operands are equal, which reduces the delay and the area needed for the calculation of the square. The squaring operation is used in many applications of high performance digital signal processors. Such applications include signal filtering, image processing and modulation of communication components. Squarers can also find applicability in several cryptographic algorithms for the implementation of modular exponentiations. The Residue Number System is an arithmetic system in which arithmetic operations can be calculated in high speed. In the RNS numbers are represented as a set of residues. In order to represent a number we define a set of pairwise relative prime integers P={p1,p2,…pk}, which is the system’s base. Every number X is represented with the set of the residues occurred after the division of X by each element of the base, P. Thus, X={x1,x2,…,xk}, where xi stands for the residue of the division of X by the ith element of the base, pi, which is denoted as Xi=|X|pi. In the RNS there is a unique representation for every integer X that 0<=X<M, where M is the product of all the elements of the base. A two-operant arithmetic operation, which can be an addition, a subtraction or a multiplication, is defined as {z1,z2,…,zk} = {x1,x2,…,xk}*{y1,y2,…,yk}, where zi = (xi*yi) modpi. Consequently, arithmetic operations are performed to parallel units (one unit for each element of the base) each one handling small residues, instead of a single unit that handles large numbers. One of the most popular base sets is those of the form {2^n, 2^n -1, 2^n+1}, due to the fact that they offer very efficient circuits when considering the area*time^2 criterion and efficient converters from/to the binary system. Thus, the design of efficient modulo (2^n-1) and modulo (2^n+1) circuits is of high importance. The problem that arises is that while in modulo(2^n) and modulo(2^n-1) arithmetic n bits are sufficient for the representation of all possible residues, in modulo(2^n+1) arithmetic (n+1) bits are needed. This can be solved by the use of the diminished-1 representation. In the diminished-1 representation every number X is represented as X-1=X-1. Therefore, n bits are sufficient for the representation, but converters from/to the diminished-1 representation are needed. In cases that the diminished-1 representation is used, operands with value 0 is treated separately. For the needs of this thesis, existing architectures of squaring circuits in the RNS are studied and new ones are proposed. The proposed architectures improve the system’s delay, while, in parallel, reduce the area needs.

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. / Arithmetic complexity is the study of the required ressources for computing poynomials using only arithmetic operations. In the last of the 70s, Valiant defined (similarly to the boolean complexity) some classes of polynomials. The polynomials which have polynomial size circuits form the class VP. Exponential sums of these polynomials correspond to the class VNP. Valiant’s hypothesis is the conjecture that VP is different tVNP.Although this conjecture is still open, it seems more accessible than its boolean counterpart. The induced algebraic structure limits the possibilities of the computation. In particular, an important result states that the low de- gree polynomials can be efficiently computed in parallel. Moreover, if we allow a fair increasement of the size, it is possible to compute them with a constant depth. As this last model is very particular, some lower bounds are known.Bürgisser showed that a conjecture (τ-conjecture) which bounds the number of roots of some univariate polynomials, implies lower bounds in arithmetic complexity. But, what happens if we try to reduce as before the depth of the circuits for the polynomials? Bounding the number of real roots of some families of polynomials would imply a separation between VP and VNP. Finally we willstudy these upper bounds on the number of real roots.

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. / 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.