95-31 Improved construction of negation-limited circuits

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