A SIMPLE LOWER BOUND FOR MONOTONE CLIQUE USING A COMMUNICATION GAME

We give a simple proof that a monotone circuit for the k-clique proble m in an n-vertex graph requires depth OMEGA(square-root k), when k les s-than-or-equal-to (3 square-root n/2)2. The proof is based on an equi valence between the depth of a Boolean circuit for a function and the number of rounds required to solve a related communication problem. Th is equivalence was shown by Karchmer and Wigderson.