Circuit booléen | EPFL Graph Search

vignette|Exemple circuit booléen à deux entrées et une sortie. Le circuit contient 3 portes logique. En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes logiques (fonctions logiques) reliées entre elles. C'est une façon de représenter une fonction booléenne. Un circuit booléen peut être utilisé pour reconnaître un langage formel, c'est-à-dire décider si un mot appartient ou non à un langage particulier. Les caractéristiques des circuits qui reconnaissent un langage permettent de définir (ou redéfinir) des classes de complexité. Les circuits booléens sont un modèle utilisé en génie informatique notamment pour la conception des unités arithmétiques et logiques et en informatique théorique notamment pour établir des bornes inférieures. Définition formelle Un circuit booléen est un graphe orienté acyclique (DAG) fini connexe dont les feuilles sont les entrées et l'unique racine est la sortie. Les sommets sont les portes, généralement

A Dichotomy for Real Weighted Holant Problems

Sangxia Huang

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks can immediately settle the complexity of all combinatorial problems expressible in that framework. Both #CSP and graph homomorphism can be viewed as subfamilies of Holant with the additional assumption that the equality constraints are always available. Other subfamilies of Holant such as Holant() and Holant (c) problems, in which we assume some specific sets of constraints to be freely available, were also studied. The Holant framework becomes more expressive and contains more interesting tractable cases with less or no freely available constraint functions, while, on the other hand, it also becomes more challenging to obtain a complete characterization of its time complexity. Recently, a complexity dichotomy for a variety of subfamilies of Holant such as #CSP, graph homomorphism, Holant(), and Holant (c) for Boolean domain was proved. In this paper, we prove a dichotomy for the general Holant framework where all the constraints are real symmetric functions on Boolean inputs. This setting already captures most of the interesting combinatorial counting problems defined by local constraints, such as (perfect) matching. This is the first time a dichotomy is obtained for general Holant problems without any auxiliary functions. One benefit of working with the Holant framework is some powerful new reduction technique such as the holographic reduction. Along the proof of our dichotomy, we introduce a new reduction technique, namely realizing a constraint function by approximating it. This new technique is employed in our proof in a situation where it seems that all previous reduction techniques fail; thus, this new idea of reduction might also be of independent interest. Besides proving a dichotomy and developing a new technique, we also obtained some interesting by-products. We prove a dichotomy for #CSP, restricting to instances where each variable appears a multiple of d times for any d. We also prove that counting the number of Eulerian orientations on 2k-regular graphs is #P-hard for any .

Springer Basel Ag2016

Design for Reliability of Nanometer-Scale Electronics under High Defect Density

Yusuf Leblebici, Alexandre Schmid, Milos Stanisavljevic

High defect density exhibited by nanoelectronic technologies, and parameter variability already affecting the operation of very-deep submicron CMOS systems demand for a combination of specific solutions, focusing at each various levels of abstraction in the development design-flow. Where traditionally applied methods fail under massive defect densities, we propose a top-down development strategy where the hardware overhead is adapted to the desired level of reliability. A CAD software tool supporting the methodology has been developed (Fig. 1(a)), with the intension to make the reliability enhancement process transparent to the designer, who is only expected to provide high-level specifications, and technology-related information as issued by foundries. The impact of sixteen mostly encountered circuit failures are evaluated using Monte Carlo SPICE simulations, and based on a replacement transistor macro-model. A fault-absorbing four-layer architecture composed of an input layer, a second layer with very limited redundant digital units (as few as one redundant unit), an analog averaging unit as third layer, and a thresholding decision unit form the architectural abstraction level [1]. After selection of the appropriate redundancy factor, the software tool partitions the initial netlist, and inserts redundant units and output layers three and four, according to a selected granularity level, which has been observed to be optimally chosen in the order of eight gate-equivalents [2]. Circuits have been developed in 180 and 90nm technologies, thus implementing all four layers at circuit abstraction level. Software simulations have been carried out validating the method on small-size circuits, in the range of Boolean gates, or a full-adder, and using single-ended and differential design styles. Monte Carlo simulations are conveniently replacing exhaustive simulation and help limit the computational burden. Comparative results are shown on Fig. 1(b), where the advantage of differential cascode switch logic (DCVS) over single-ended CMOS is evidenced. A large-scale AES crypto-chip based on the proposed method is currently in fabrication; the proposed method and software tool have been applied in the development of robust standard cells.

2006

A Dichotomy for Real Weighted Holant Problems

Sangxia Huang

Springer Basel Ag2016

Design for Reliability of Nanometer-Scale Electronics under High Defect Density

Yusuf Leblebici, Alexandre Schmid, Milos Stanisavljevic

2006