Publication

On the Number of Containments in P-free Families

Publications associées (41)

Graph Chatbot

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.

Connectez-vous pour utiliser Chat avec Graph Search

In Medio Stat Virtus: Combining Boolean and Pattern Matching

Giovanni De Micheli, Alessandro Tempia Calvino, Gianluca Radi

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

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

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

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

Raffaele Marino

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

Packing the Boolean lattice with copies of a poset

Istvan Tomon

The Boolean lattice (2[n],subset of) is the family of all subsets of [n]={1,MIDLINE HORIZONTAL ELLIPSIS,n}, ordered by inclusion. Let P be a partially ordered set. We prove that if n is sufficiently large, then there exists a packing P of copies of P in (2 ...

WILEY2020

A simple proof for a forbidden subposet problem

Abhishek Methuku

The poset Y-k,Y-2 consists of k + 2 distinct elements x(1), x(2), ..., x(k), y(1), y(2), such that x(1)

ELECTRONIC JOURNAL OF COMBINATORICS2020

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

New dense superball packings in three dimensions

Maria Margarethe Dostert

We construct a new family of lattice packings for superballs in three dimensions (unit balls for the l(3)(p) norm) with p epsilon (1, 1.58]. We conjecture that the family also exists for p epsilon (1.58, log(2) 3 = 1.5849625 ...]. Like in the densest latti ...

WALTER DE GRUYTER GMBH2020

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