The Complexity of Self-Dual Monotone 7-Input Functions

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.

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

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

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

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

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

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

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

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

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

The Complexity of Self-Dual Monotone 7-Input Functions

Chat with Graph Search

Formula Normalizations in Verification

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

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

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

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

Three-Input Gates for Logic Synthesis

Une approche computationnelle du cadastre napoléonien de Venise

Covers Of Rational Double Points In Mixed Characteristic

A Majority Lemma for Randomised Query Complexity