A Note on the Bottleneck Counting Argument (Extended Abstract)
Janoš Šimon, Shi‐Chun Tsai · 1997
Both the bottleneck counting argument [5, 61 and Razborov’s approximation method [I, 3,8] have been used to prove exponential lower bounds for monotone circuits. We show that under the monotone circwit 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-CL.IQUE,, problem by the bottleneck counting argument.