We develop a new and simple way to describe Karatsuba-like algorithms for multiplication of polynomials over$\mathbb {F}_2$. We restrict the search of small circuits to a class of circuits we callsymmetric bilinear. These are circuits in which AND gates only compute functions of the form$\sum _{i \in S} a_i \cdot \sum _{i \in S} b_i \quad \quad (S \subseteq \lbrace 0, \ldots, n-1\rbrace).$∑i∈Sai·∑i∈Sbi(S⊆{0,...,n-1}).These techniques yield improved recurrences for$M(kn)$M(kn), the number of gates used in a circuit that multiplies two$kn$kn-term polynomials, for$k = 4,5,6,$k=4,5,6,and 7. We built and verified the circuits for$n$n-term binary polynomial multiplication for values of$n$nof practical interest. Circuits for$n$nup to 100 are posted athttp://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/BinPolMult.tar.gz.

We consider Boolean circuits over the full binary basis. We prove a (3+1/86)n-o(n) lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the 3n-o(n) bound of Norbert Blum (1984).The proof is based on the gate elimination technique extended with the following three ideas. We generalize the computational model by allowing circuits to contain cycles, this in turn allows us to perform affine substitutions. We use a carefully chosen circuit complexity measure to track the progress of the gate elimination process. Finally, we use quadratic substitutions that may be viewed as delayed affine substitutions.