@inproceedings{94e8fd9c476543abad69d79d4d68085b,

title = "A note on the bottleneck counting argument",

abstract = "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-CLIQUEn problem by the bottleneck counting argument.",

author = "J. Simon and Shi-Chun Tsai",

note = "Publisher Copyright: {\textcopyright} 1997 IEEE.; 12th Annual IEEE Conference on Computational Complexity, CCC 1997 ; Conference date: 24-06-1997 Through 27-06-1997",

year = "1997",

doi = "10.1109/CCC.1997.612324",

language = "English",

series = "Proceedings of the Annual IEEE Conference on Computational Complexity",

publisher = "IEEE Computer Society",

pages = "297--301",

booktitle = "Proceedings - 12th Annual IEEE Conference on Computational Complexity, CCC 1997 (Formerly: Structure in Complexity Theory Conference)",

address = "United States",

}