Abstract
Given a linear boolean operator, how to compute it by a small circuit using only unbounded fanin addition gates? Since this is one of the simplest and most basic circuit models, the question was considered by many authors since early 1950s. This led to a variety of upper and lower bound arguments---ranging from algebraic (determinant and matrix rigidity), to combinatorial (Ramsey properties, coverings and decompositions) to graph-theoretic (the superconcentrator method). We give a throughout survey of the research in this direction, and prove some new results to fill out the picture. The focus is on the cases when the addition operation is either the boolean OR or XOR, but the model in which arbitrary boolean functions are allowed as gates is considered as well.