Theory of Computing Systems manuscript No. (will be inserted by the editor) New Lower Bounds on Circuit Size of Multi-output Functions

Abstract Let Bn,m be the set of all Boolean functions from {0, 1}n to {0, 1}m, Bn = Bn,1 and U2 = B2 \ {⊕,≡}. In this paper, we prove the following two new lower bounds on the circuit size over U2. 1. A lower bound CU2(f) ≥ 5n−o(n) for a linear function f ∈ Bn−1,logn. The10 lower bound follows from the following more general result: for any matrix A ∈ {0, 1}m×n with n pairwise different non-zero columns and b ∈ {0, 1}m, CU2(Ax ⊕ b) ≥ 5(n−m). 2. A lower bound CU2(f) ≥ 7n − o(n) for f ∈ Bn,n. Again, this is a conse-quence of the following result: for any f ∈ Bn satisfying a certain simple15 property, CU2(g(f)) ≥ min{CU2(f |xi=a,xj=b) : xi 6 = xj, a, b, ∈ {0, 1}}+ 2n−Θ(1) Research results presented in section 4.1 are obtained with a partial support of the Govern