Stasys Jukna

A Criterion for Monotone Circuit Complexity

Abstract

In this paper we study the lower bounds problem for monotone circuits.
We first extend the famous method of approximations due to Razborov
from  monotone computations over Boolean lattices to  monotone computations 
over semilattices, including the semilattice of non-monotone DNFs.

Our second result is tractable combinatorial criterion for the 
monotone circuit complexity. The criterion is symmetric and yields 
(in a uniform  and easy way) all the lower bounds obtained before,
except Razborov's superpolynomial lower bound for the Perfect Matching
function.  


[Unpublished manuscript, 1991]