On the bottleneck counting argument

Both the bottleneck counting argument (Haken, Theoret. Comput. Sci, 39 (198 5) 297-308; Proc. 36th Symp. of Foundations of Computer Science, 1995, pp. 36-34) and Razborov's approximation method (Alon and Boppana, Combinatorica 7(1) (1987) 1-22; Andreev, Soviet Math. Dokl 31(1985) 530-534; Rayborov, S oviet Math. Dokl 31 (1985) 354-357) have been used to prove exponential low er bounds for monotone circuits. We show that under the monotone circuit mo del for every proof by the approximation method, there is a bottleneck coun ting proof and vice versa, We also illustrate the elegance of the bottlenec k counting technique with a simple self-explained example: the proof of a ( previously known) lower bound fur the 3-CLIQUE(n) problem by the bottleneck counting argument. (C) 2000 Elsevier Science B.V. All rights reserved.