  We use critical block sensitivity, a new complexity measure introduced by
Huynh and Nordstr\"om (STOC 2012), to study the communication complexity of
search problems. To begin, we give a simple new proof of the following central
result of Huynh and Nordstr\"om: if $S$ is a search problem with critical block
sensitivity $b$, then every randomised two-party protocol solving a certain
two-party lift of $S$ requires $\Omega(b)$ bits of communication. Besides
simplicity, our proof has the advantage of generalising to the multi-party
setting. We combine these results with new critical block sensitivity lower
bounds for Tseitin and Pebbling search problems to obtain the following
applications:
  (1) Monotone Circuit Depth: We exhibit a monotone $n$-variable function in NP
whose monotone circuits require depth $\Omega(n/\log n)$; previously, a bound
of $\Omega(\sqrt{n})$ was known (Raz and Wigderson, JACM 1992). Moreover, we
prove a $\Theta(\sqrt{n})$ monotone depth bound for a function in monotone P.
  (2) Proof Complexity: We prove new rank lower bounds as well as obtain the
first length--space lower bounds for semi-algebraic proof systems, including
Lov\'asz--Schrijver and Lasserre (SOS) systems. In particular, these results
extend and simplify the works of Beame et al. (SICOMP 2007) and Huynh and
Nordstr\"om.
