We present a new method for obtaining lower bounds on communication complexity. Our method is based on associating with a
binary function
f a graph
G
f
such that log
χ(
G
f
) captures
N
0(
f) +
N
1(
f). Here
χ(
G) denotes the chromatic number of
G, and
N
0(
f) and
N
1(
f) denote, respectively, the nondeterministic communication complexity of
[`(f)]\overline{f}
and
f. Thus log
χ(
G
f
) is a lower bound on the deterministic as well as zero-error randomized communication complexity of
f. Our characterization opens the possibility of using various relaxations of the chromatic number as lower bound techniques
for communication complexity. In particular, we show how various (known) lower bounds can be derived by employing the clique
number, the Lovász
ϑ-function, and graph entropy lower bounds on the chromatic number.
This work was performed while the authors were at IBM Almaden.