On a small class of Boolean sums

AbstractIn this paper, we prove that almost all members of a certain natural class of n-input, n-output Boolean sums of cardinality 2n have monotone circuit complexity n22O((log log n)2). As a corollary, it is shown that there is a linear space computable Boolean sum whose monotone complexity is n22O((log log n)2) The main combinatorial achievement in the paper is as follows. For a subset D of [n],11We use [n] to denote the set 0,…,n - 1. denote by s(D) the largest integer k such that EA, B∥A∥ = ∥B∥ = k & A + B ⊆ D. We prove that s(D) = 2O((log log n)2) for almost all D