Tata Institute of Fundamental Research
Size-energy Tradeoffs for Unate Circuits Computing Symmetric Boolean Functions
Student Seminar
Speaker:
Pritam Bhattacharya
Organiser:
Swagato Sanyal
Date:
Friday, 7 Sep 2012, 15:00 to 16:30
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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
| Speaker: | Pritam Bhattacharya |
| Organiser: | Swagato Sanyal |
| Date: | Friday, 7 Sep 2012, 15:00 to 16:30 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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