We shall show that any monotone circuit (with fan-in 2) which determines if a graph has a perfect matching must have depth . This shows that efficient deterministic parallel algorithms for the perfect matching problem must use negation. To do so, we shall use tools from communication complexity: more specifically, we shall show that such a circuit will imply a low-cost communication protocol for set-disjointness, which is known to be hard.
