The Power of Negative Thinking in Multiplying Boolean Matrices
Vaughan Pratt · SIAM Journal on Computing · 1975
We show that $n^3 $ distinct and-gate inputs appear in any circuit constructed from and-gates and or-gates that computes the product of two $n \times n$ Boolean matrices. Using not-gates as well, it is possible to realize a circuit for this problem using only $O(n^{\log _2 7} \log ^2 n)$ gates, whence we infer a much larger complexity gap between and-or and and-or-not circuits than was previously known.