Publications related to Parity function

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

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Parity function

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

Chat with Graph Search

Nonsilicon, Non-von Neumann Computing—Part I

A Majority Lemma for Randomised Query Complexity

A Hybrid Method for Spectral Translation Equivalent Boolean Functions

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

Majority Logic Synthesis

Pairs of majority-decomposing functions

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

A Spectral Algorithm for 3-valued Function Equivalence Classification

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