## DIMACS TR: 95-31

## Improved construction of negation-limited circuits

### Author: Robert Beals

**
ABSTRACT
**

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
by Berkowitz).

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-31.ps.gz

DIMACS Home Page