A note on the bottleneck counting argument
Janoš Šimon, Shi‐Chun Tsai · 1997
Both the bottleneck counting argument and Razborov's approximation method have been used to prove exponential lower bounds for monotone circuits. We show that under the monotone circuit model for every proof by the approximation method, there is a bottleneck counting proof and vice versa. We also illustrate the elegance of the bottleneck counting technique with a simple self-explained example: the proof of a (previously known) lower bound for the 3-CLIQUE/sub n/ problem by the bottleneck counting argument.