  We show that almost all known lower bound methods for communication
complexity are also lower bounds for the information complexity. In particular,
we define a relaxed version of the partition bound of Jain and Klauck and prove
that it lower bounds the information complexity of any function. Our relaxed
partition bound subsumes all norm based methods (e.g. the factorization norm
method) and rectangle-based methods (e.g. the rectangle/corruption bound, the
smooth rectangle bound, and the discrepancy bound), except the partition bound.
Our result uses a new connection between rectangles and zero-communication
protocols where the players can either output a value or abort. We prove the
following compression lemma: given a protocol for a function f with information
complexity I, one can construct a zero-communication protocol that has
non-abort probability at least 2^{-O(I)} and that computes f correctly with
high probability conditioned on not aborting. Then, we show how such a
zero-communication protocol relates to the relaxed partition bound. We use our
main theorem to resolve three of the open questions raised by Braverman. First,
we show that the information complexity of the Vector in Subspace Problem is
{\Omega}(n^{1/3}), which, in turn, implies that there exists an exponential
separation between quantum communication complexity and classical information
complexity. Moreover, we provide an {\Omega}(n) lower bound on the information
complexity of the Gap Hamming Distance Problem.
