Publication

The Complexity of Self-Dual Monotone 7-Input Functions

Related publications (29)

Formula Normalizations in Verification

Viktor Kuncak, Mario Bucev, Simon Guilloud, Dragana Milovancevic

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

2023

A roadmap to understanding diversity and function of coral reef-associated fungi

Claudia Isabella Pogoreutz

Tropical coral reefs are hotspots of marine productivity, owing to the association of reef-building corals with endosymbiotic algae and metabolically diverse bacterial communities. However, the functional importance of fungi, well-known for their contribut ...

OXFORD UNIV PRESS2022

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Viktor Kuncak, Simon Guilloud

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

Springer2022

Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions

Andreas Loukas, Nikolaos Karalias

Integrating functions on discrete domains into neural networks is key to developing their capability to reason about discrete objects. But, discrete domains are (I) not naturally amenable to gradient-based optimization, and (II) incompatible with deep lear ...

2022

A chance-constraint approach for optimizing Social Engagement-based services

Michel Bierlaire, Edoardo Fadda

Social Engagement is a novel business model transforming final users of a service from passive into active components. In this framework, people are contacted by a company and they are asked to perform tasks in exchange for a reward. This arises the compli ...

IEEE2022

Three-Input Gates for Logic Synthesis

Giovanni De Micheli, Eleonora Testa, Mathias Soeken, Dewmini Sudara Marakkalage, 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

Une approche computationnelle du cadastre napoléonien de Venise

Frédéric Kaplan, Raphaël Barman, Isabella Di Lenardo, Federica Pardini

At the beginning of the 19th century, the Napoleonic administration introduced a new standardised description system to give an objective account of the form and functions of the city of Venice. The cadastre, deployed on a European scale, was offering for ...

2021

Covers Of Rational Double Points In Mixed Characteristic

Javier Alonso Carvajal Rojas

We further the classification of rational surface singularities. Suppose (S, n, k) is a 3-dimensional strictly Henselian regular local ring of mixed characteristic (0, p > 5). We classify functions f for which S/(f) has an isolated rational singularity at ...

2021

A Majority Lemma for Randomised Query Complexity

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

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