The fascinating properties of MAJority

Post doctoral researcher
Integrated Systems Laboratory
EPFL

 

Webpage

Thursday, 28 September 2017 at 11:40 in room BC 420

Abstract:

The ternary majority function has fascinated researchers in computer science and mathematics for many decades. This is due to its fascinating properties, which are discovered and rediscovered again and again over the years. The majority function evaluates to true if two or three of its arguments evaluate to true. Together with inversion, it supports a complete axiomatic system which makes it particularly interesting in logic optimisation. In the talk we will stop over at various corners in the history of majority logic synthesis. The descriptions include synthesis algorithms, function decompositions, and a card trick that was used by Ea Ea (formerly Craige Schensted) to raise the interest for majority logic to Martin Gardner in one of their letter exchanges.

 

About the speaker:

Mathias Soeken works as a researcher at the Integrated Systems Laboratory at EPFL, Lausanne, Switzerland in the group of Giovanni De Micheli. From 2009 to 2015 he worked at the University of Bremen, Germany in the group of Rolf Drechsler. Since 2014, he is a regularly visiting post doc at UC Berkeley, CA, USA in the group of Robert K. Brayton. He holds a Ph.D. degree (Dr.-Ing.) in Computer Science from University of Bremen, Germany (2013). His research interests are logic synthesis, reverse engineering, formal verification, and quantum computing.