Publications associées à Fonction parité

A Majority Lemma for Randomised Query Complexity

Mika Tapani Göös, Gilbert Théodore Maystre

We show that computing the majority of n copies of a boolean function g has randomised query complexity R(Maj∘gⁿ) = Θ(n⋅R ̅_{1/n}(g)). In fact, we show that to obtain a similar result for any composed function f∘gⁿ, it suffices to prove a sufficiently stro ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021

From Boolean functions to quantum circuits: A scalable quantum compilation flow in C++

Giovanni De Micheli, Fereshte Mozafari Ghoraba, Heinz Riener, Giulia Meuli, Bruno Schmitt Antunes

We propose a flow for automated quantum compila- tion. Our flow takes a Boolean function implemented in Python as input and translates it into a format appropriate for reversible logic synthesis. We focus on two quantum compilation tasks: uniform state pre ...

2021

A Spectral Algorithm for 3-valued Function Equivalence Classification

Mathias Soeken

Spectral techniques for Boolean and multiple-valued functions have been well studied and found to be useful in logic design and testing for conventional circuits. Spectral techniques also have potential application for reversible and quantum circuits. This ...

OLD CITY PUBLISHING INC2020

Exact Synthesis of Boolean Functions in Majority-of-five Forms

Giovanni De Micheli, Mathias Soeken, Winston Jason Haaswijk, Zhufei Chu

Recent studies show that majority-based logic synthesis is beneficial for both traditional and nanotechnology digital designs. However, most of the existing synthesis algorithms for majority logic generate majority-of-three (M-3) networks. The optimization ...

IEEE2019

A Hybrid Method for Spectral Translation Equivalent Boolean Functions

Giovanni De Micheli, Mathias Soeken, Eleonora Testa

The equivalence of Boolean functions with respect to five invariance (aka translation) operations has been well considered with respect to the Rademacher-Walsh spectral domain. In this paper, we introduce a hybrid approach that uses both the Reed-Muller an ...

IEEE2019

Majority Logic Synthesis

Giovanni De Micheli, Mathias Soeken, Luca Gaetano Amarù, Eleonora Testa, Odysseas Zografos

The majority function (xyz) evaluates to true, if at least two of its Boolean inputs evaluate to true. The majority function has frequently been studied as a central primitive in logic synthesis applications for many decades. Knuth refers to the majority f ...

ASSOC COMPUTING MACHINERY2018

Pairs of majority-decomposing functions

Giovanni De Micheli, Mathias Soeken, Eleonora Testa

We are interested in decompositions xnf1f2 of the majority function over n odd arguments x1, ...,xnsuch that f1and f2do not depend on xn. In this paper, we derive the conditions for f1and f2that satisfy the decomposition. Such decompositions play a centr ...

2018

Size Optimization of MIGs with an Application to QCA and STMG Technologies

Giovanni De Micheli, Mathias Soeken, Luca Gaetano Amarù, Eleonora Testa, Heinz Riener

Majority-inverter graphs (MIGs) are a logic representation with remarkable algebraic and Boolean properties that enable efficient logic optimizations beyond the capabilities of traditional logic representations. Further, since many nano-emerging technologi ...

ASSOC COMPUTING MACHINERY2018

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Fonction parité

Symmetry in design and decoding of polar-like codes

A Majority Lemma for Randomised Query Complexity

From Boolean functions to quantum circuits: A scalable quantum compilation flow in C++

A Spectral Algorithm for 3-valued Function Equivalence Classification

Exact Synthesis of Boolean Functions in Majority-of-five Forms

A Hybrid Method for Spectral Translation Equivalent Boolean Functions

Majority Logic Synthesis

Nonsilicon, Non-von Neumann Computing—Part I

Pairs of majority-decomposing functions

Size Optimization of MIGs with an Application to QCA and STMG Technologies

Graph Chatbot

Chattez avec Graph Search

Symmetry in design and decoding of polar-like codes

A Hybrid Method for Spectral Translation Equivalent Boolean Functions

From Boolean functions to quantum circuits: A scalable quantum compilation flow in C++

A Majority Lemma for Randomised Query Complexity

A Spectral Algorithm for 3-valued Function Equivalence Classification

Nonsilicon, Non-von Neumann Computing—Part I

Pairs of majority-decomposing functions

Size Optimization of MIGs with an Application to QCA and STMG Technologies

Exact Synthesis of Boolean Functions in Majority-of-five Forms

Majority Logic Synthesis