# Size-energy Tradeoffs for Unate Circuits Computing Symmetric Boolean Functions

Speaker:

## Time:

Friday, 7 September 2012, 15:00 to 16:30

## Venue:

• A-212 (STCS Seminar Room)

## Organisers:

A unate gate is a logical gate computing a unate Boolean function, which is monotone in each variable. Examples of unate gates are AND gates, OR gates, NOT gates, threshold gates etc. A unate circuit $C$ is a combinatorial logic circuit consisting of unate gates. Let $f$ be a symmetric Boolean function of $n$ variables. Let $m0$ and $m1$ be the maximum number of consecutive $0s$ and consecutive 1s in the value vector $v(f)$ of $f$, respectively. Also, let $l=min{m0,m1}$ and $m=max{m0,m1}$. Now, let $C$ be a unate circuit computing $f$. Let $s$ be the size of the circuit $C$, that is, $C$ consists of $s$ unate gates. If we define the maximum number of gates outputting '1' over all inputs to $C$ to be the energy $e$ of the circuit $C$, then we can show that there exists a tradeoff between the size $s$ and the energy $e$ of $C$. More precisely, we will show the following - $(n+1-l)/m <= s^e$. We will also present lower bounds on the size $s$ of a unate circuit $C$ represented in terms of $n$, l and $m$.