New Lower Bounds on Circuit Size of Multi-output Functions

作者：Demenkov Evgeny^*; Kulikov Alexander S; Melanich Olga; Mihajlin Ivan

来源：Theory of Computing Systems, 2015, 56(4): 630-642.

DOI：10.1007/s00224-014-9590-4

• Circuit complexity
• Lower bounds
• Boolean functions
• Gate elimination

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)).

• 出版日期2015-5