Theory Talk
Thursday, November 5, 2009
4:00 p.m., AKW 200

Speaker: René Peralta, National Institute of Standards and Technology (NIST)
Title: Small Circuits for Boolean Functions

Abstract: We consider the problem of building efficient circuits using arithmetic modulo 2. This problem is highly intractable for any meaningful measure of “efficiency”. Thus, we can only hope to develop heuristics. We propose the following approach:

1. find a circuit with as few multiplications as possible; then
2. optimize the linear pieces of this circuit.

The multiplicative complexity of a function is the number of multiplications necessary and sufficient to compute it.

For example, the function: f(x1,x2,x3) = x1x2 + x1x3 + x2x3 can be computed using only one multiplication:



Too easy? Then try the following one using 3 multiplications only:



I will discuss known bounds on the multiplicative complexity of functions. Some of these results are constructive, and thus can be used in the first step of our circuit optimization method.

The second part of the talk considers the problem of optimizing the linear parts of a circuit. In this problem, we are given a binary m-by-n matrix M, and the task is to build a circuit for computing Mx (where x is an n-bit input). It turns out most work in this area makes an implicit assumption that turns out to be false. When one sheds this assumption, it becomes clear that new heuristics are needed. We have coded one such heuristic. I will report on how it fares compared to traditional methods. This is joint work with Joan Boyar, of the University of Southern Denmark.