A Majority Lemma for Randomised Query Complexity

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

By juxtaposing ideas from fractal geometry and dynamical systems, Furstenberg proposed a series of conjectures in the late 1960's that explore the relationship between digit expansions with respect to multiplicatively independent bases. In this work, we in ...

Factored form is a powerful multi-level representation of a Boolean function that readily translates into an implementation of the function in CMOS technology. In particular, the number of literals in a factored form correlates strongly with the number of ...

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...

Approximate logic synthesis is an emerging field that tolerates errors in the synthesized logic circuits for better optimization quality. Indeed, in many computing problems, the requirement of preserving the exact functionality either results in unnecessar ...

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

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

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

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

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

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

Logic synthesis is a key component of digital design and modern EDA tools; it is thus an essential instrument for the design of leading-edge chips and to push the limits of their performance. In the last decades, the electronic circuits community has evolv ...

Suppose we have randomized decision trees for an outer function f and an inner function g. The natural approach for obtaining a randomized decision tree for the composed function (f∘ gⁿ)(x¹,…,xⁿ) = f(g(x¹),…,g(xⁿ)) involves amplifying the success probabili ...

Most quantum algorithms assume some specific initial state in superposition of basis states before performing the desired application-specific computations. The preparation of such states itself requires a computation performed by a quantum circuit. In thi ...

Logic synthesis is a fundamental step in the realization of modern integrated circuits. It has traditionally been employed for the optimization of CMOS-based designs, as well as for emerging technologies and quantum computing. Recently, it found applicatio ...

A subfamily {F-1, F-2, ..., F-vertical bar P vertical bar} subset of F is a copy of the poset P if there exists a bijection i : P -> {F-1, F-2, ..., F-vertical bar P vertical bar}, such that p

The study of the complexity of Boolean functions has recently found applications in logic synthesis and optimization algorithms, as for instance in logic rewriting. Previous works have focused on the minimum length of Boolean chains for functions up to 5 i ...

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

Today, the design of electronic systems is largely automated. The practice of using software automation technologies for the design of electronic hardware is commonly referred to as Electronic Design Automation (EDA). EDA comprises a large set of tools, fr ...

A Majority Lemma for Randomised Query Complexity

Chat with Graph Search

In Medio Stat Virtus: Combining Boolean and Pattern Matching

Additive and geometric transversality of fractal sets in the integers

Improving Standard-Cell Design Flow using Factored Form Optimization

Formula Normalizations in Verification

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Logic Synthesis From Incomplete Specifications Using Disjoint Support Decomposition

Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition

Three-Input Gates for Logic Synthesis

Learning from survey propagation: a neural network for MAX-E-3-SAT

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

Enumerating Optimal Quantum Circuits using Spectral Classification

Advanced Functional Decomposition Using Majority and Its Applications

Data Structures and Algorithms for Logic Synthesis in Advanced Technologies

When Is Amplification Necessary for Composition in Randomized Query Complexity?

Automatic Uniform Quantum State Preparation Using Decision Diagrams

A Logic Synthesis Toolbox for Reducing the Multiplicative Complexity in Logic Networks

On the Number of Containments in P-free Families

The Complexity of Self-Dual Monotone 7-Input Functions

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

SAT-Based Exact Synthesis for Multi-Level Logic Networks