New Lower Bounds on Circuit Size of Multi-output Functions

Let B (n, m) be the set of all Boolean functions from {0, 1}(n) to {0, 1}(m) , B-n = B-n,B- 1 and U-2 = B-2 \ {circle plus, equivalent to}. In this paper, we prove the following two new lower bounds on the circuit size over U-2. 1. A lower bound C-U2 (f) >= 5n - o(n) for a linear function f is an element of B-n-1,B-log (n) . The lower bound follows from the following more general result: for any matrix A is an element of {0, 1}(mxn) with n pairwise different non-zero columns and b is an element of {0, 1}(m) , C(U2()Ax circle plus b) >= 5(n - m). 2. A lower bound C-U2 (f) >= 7n - o(n) for f is an element of B-n,B-n. Again, this is a consequence of the following result: for any f is an element of B-n satisfying a certain simple property, C-U2 (g(f)) >= min{C-U2 (f vertical bar(xi=a, xj=b)) : x(i) not equal x(j), a, b, is an element of{0, 1}} + 2n - Theta(1) where g(f) is an element of B-n,B- n is defined as follows: g(f) = (f circle plus x(1), ... , f circle plus x(n)) (to get a 7n - o(n) lower bound it remains to plug in a known function f is an element of B-n,B- 1 with C-U2 (f) >= 5n - o(n)).