DIMACS TR: 95-31
Improved construction of negation-limited circuits
Author: Robert Beals
A theorem of Markov states that any system of boolean functions
on n variables may be computed by a boolean circuit containing
at most log(n+1) negation gates. We call such a circuit negation
limited. A circuit with inputs x_1, ..., x_n and outputs
neg(x_1), ..., neg(x_n) is called an inverter. Fischer has constructed
negation-limited inverters of size 0(n^2 log n) and depth 0(log n).
Recently, Tanaka and Nishino have reduced the circuit size to
0(n log^2 n) at the expense of increasing the depth to log^2 n.
We construct negation-limited inverters of size 0(n log n), with
depth only 0(log n). We also improve a technique of Valiant
for constructing monotone circuits for slice functions (introduced
Paper available at:
DIMACS Home Page