Negation is Powerless for Boolean Slice Functions

Leslie Gabriel Valiant · SIAM Journal on Computing · 1986

It is shown that for any slice function of n variables the monotone circuit complexity exceeds the circuit complexity over a universal basis by at most a multiplicative constant factor and an additive term of order $O(n(\log n)^2 )$.

Read the paper · More papers on PaperTik