**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Person# Mathias Soeken

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units

Loading

Courses taught by this person

Loading

Related research domains

Loading

Related publications

Loading

People doing similar research

Loading

Related units (4)

Related publications (104)

Loading

Loading

Loading

Related research domains (57)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algo

Quantum computing

A quantum computer is a computer that exploits quantum mechanical phenomena.
At small scales, physical matter exhibits properties of both particles and waves, and quantum computing leverages this beh

Experiment

An experiment is a procedure carried out to support or refute a hypothesis, or determine the efficacy or likelihood of something previously untried. Experiments provide insight into cause-and-effe

People doing similar research (98)

Courses taught by this person (1)

Logic synthesis describes techniques to map complex functionality into a sequence of a few, simple, and small logic primitives. It finds application dominantly in digital design, but is most recently also frequently used in cryptography and quantum computing.

Spectral techniques for Boolean and multiple-valued functions have been well studied and found to be useful in logic design and testing for conventional circuits. Spectral techniques also have potential application for reversible and quantum circuits. This paper addresses the classification of 3-valued functions into spectral translation equivalence classes. A transform algorithm is presented that determines the spectral translations to map a given function to the representative function for the equivalence class containing the given function. Using this algorithm we show, by exhaustive enumeration, that the 2-variable 3-valued functions partition into 11 equivalence classes. The number of 3-valued functions with 3 or more variables is very large, prohibiting exhaustive enumeration. We show that a search of 3-valued function 1-neighbourhoods yields 167,266 equivalence classes for 3 variables. The transform algorithm can be used for a higher number of variables to determine if two functions fall within the same equivalence class and, if they do, to find a sequence of spectral translations to map one to the other.

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

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 primarily on graphs with 2-input nodes such as AND and OR gates, the recently proposed paradigm of Majority-Inverter Graphs (MIGs) instead uses the 3-input Majority gate as the node function. As this technique proved to be a success, it is natural to ask: are there other 3-input gates better suited for logic synthesis? Motivated by this question, we investigate the relative advantages of 3-input gates as constituents of logic networks. We consider representative gates from each of the ten nondegenerate 3-input NPN classes and study how powerful they are at representing Boolean functions. Using SAT-based exact synthesis, we evaluate each 3-input gate using the minimum number of such gates (together with inverters) needed to synthesize all 4-input Boolean functions and a subset of frequent 5-input and 6-input Boolean functions. We show that the logic gate Dot(x,y, z) := x circle plus (z boolean OR xy) outperforms the rest in terms of expressive power. We further confirm this observation by showing that Dot-Inverter Graph representations are more than 14% smaller as compared to MIG representations of EPFL benchmarks.

Luca Gaetano Amarù, Giovanni De Micheli, Heinz Riener, Mathias Soeken, Eleonora Testa

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 application in minimizing the number of AND gates in cryptography benchmarks represented as xor-and graphs (XAGs). The number of AND gates in an XAG, which is called the logic network's multiplicative complexity, plays a critical role in various cryptography and security protocols such as fully homomorphic encryption (FHE) and secure multi-party computation (MPC). Further, the number of AND gates is also important to assess the degree of vulnerability of a Boolean function, and influences the cost of techniques to protect against side-channel attacks. However, so far a complete logic synthesis flow for reducing the multiplicative complexity in logic networks did not exist or relied heavily on manual manipulations. In this paper, we present a logic synthesis toolbox for cryptography and security applications. The proposed tool consists of powerful transformations, namely resubstitution, refactoring, and rewriting, specifically designed to minimize the multiplicative complexity of an XAG. Our flow is fully automatic and achieves significant results over both EPFL benchmarks and cryptography circuits. We improve the best-known results for cryptography up to 59%, resulting in a normalized geometric mean of 0.82.

2020