Publication

A Majority Lemma for Randomised Query Complexity

Related publications (33)

Graph Chatbot

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.

, ,

Technology mapping transforms a technology-independent representation into a technology-dependent one given a library of cells. This process is performed by means of local replacements that are extracted by matching sections of the subject graph to library ...

2024

, ,

Logic resynthesis is the problem of finding a dependency function to re-express a given Boolean function in terms of a given set of divisor functions. In this paper, we study logic resynthesis of majority-based circuits, which is motivated by the increasin ...

IEEE2021

Three-Input Gates for Logic Synthesis

Giovanni De Micheli, Mathias Soeken, Dewmini Sudara Marakkalage, Eleonora Testa, Heinz Riener

Most logic synthesis algorithms work on graph representations of logic functions with nodes associated with arbitrary logic expressions or simple logic functions and iteratively optimize such graphs. While recent multilevel logic synthesis efforts focused ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

Many natural optimization problems are NP-hard, which implies that they are probably hard to solve exactly in the worst-case. However, it suffices to get reasonably good solutions for all (or even most) instances in practice. This paper presents a new algo ...

IOP PUBLISHING LTD2021

Enumerating Optimal Quantum Circuits using Spectral Classification

Giovanni De Micheli, Mathias Soeken, Giulia Meuli

This work targets fault-tolerant quantum computing and focuses on the problem of mapping reversible circuits into the Clifford+T quantum gate library. We present an automatically-generated database containing minimal-cost quantum circuits for Boolean funct ...

IEEE2020

Enumerating Optimal Quantum Circuits using Spectral Clasification

Giovanni De Micheli, Mathias Soeken, Giulia Meuli

2020

The Power of Many Samples in Query Complexity

Mika Tapani Göös

The randomized query complexity 𝖱(f) of a boolean function f: {0,1}ⁿ → {0,1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution 𝒟₀ over 0-inputs from a distribution 𝒟₁ over 1-inputs, maximized ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2020

Advanced Functional Decomposition Using Majority and Its Applications

Giovanni De Micheli, Mathias Soeken, Zhufei Chu

Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and the 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such a de ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

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

Exact Synthesis of ESOP Forms

Giovanni De Micheli, Heinz Riener, Bruno Schmitt Antunes

We present an exact synthesis approach for computing Exclusive-or Sum-of-Products (ESOP) forms with a minimum number of product terms using Boolean satisfiability. Our approach finds one or more ESOP forms for a given Boolean function. The approach can dea ...

Springer2019