On Proving Lower Bounds for Circuit Size
Mauricio Karchmer · Birkhäuser Boston eBooks · 1995
In [5], Razborov showed that the clique function cannot be computed by polynomial size monotone circuits. The method of proof, called thereafter the approximation method , provided lower bounds for other problems as well (see Razborov [6]) and was later used by Alon & Boppana [1] to show that the clique function requires exponential size monotone circuits.