Communication Lower Bounds Via the Chromatic Number
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)
- PDF / 461,067 Bytes
- 13 Pages / 430 x 660 pts Page_size
- 51 Downloads / 217 Views
Yahoo! Research [email protected] 2 Google, Inc. [email protected]
Abstract. 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 Gf such that log χ(Gf ) captures N0 (f ) + N1 (f ). Here χ(G) denotes the chromatic number of G, and N0 (f ) and N1 (f ) denote, respectively, the nondeterministic communication complexity of f and f . Thus log χ(Gf ) 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´ asz ϑ-function, and graph entropy lower bounds on the chromatic number.
1
Introduction
Consider two computationally unbounded players Alice and Bob who wish to jointly evaluate a binary function f (x, y), where Alice holds the input x and Bob holds y. The central question in communication complexity [1] is the number of bits Alice and Bob need to exchange to compute f (x, y). Besides being a natural concrete computational model to study, lower bounds in communication complexity have deep connections to time-space tradeoffs, decision trees, circuit lower bounds, and pseudorandomness. For an excellent account, see the book by Kushilevitz and Nisan [2]. We develop a new and general method for proving communication complexity lower bounds for Boolean functions. Our method is based on associating a natural graph Gf for every Boolean function f such that the chromatic number of Gf precisely captures the sum (or max) of the nondeterministic and co-nondeterministic communication complexity of f . Thus, it implies a lower bound on the usual, deterministic, communication complexity of f . While lower bounding χ(Gf ) could be hard in general, the fact that it is a well-studied graphtheoretic quantity opens up a whole new set of tools in the study of communication complexity; these tools include well-known relaxations of the chromatic
This work was performed while the authors were at IBM Almaden.
V. Arvind and S. Prasad (Eds.): FSTTCS 2007, LNCS 4855, pp. 228–240, 2007. c Springer-Verlag Berlin Heidelberg 2007
Communication Lower Bounds Via the Chromatic Number
229
number such as the Lov´ asz theta function, graph entropy, linear programming relaxations, etc. We illustrate our method via simple examples. One of our examples shows the use of Lov´ asz theta function — which satisfies χ(Gf ) ≥ ϑ(Gf ) — to lower bound χ(Gf ). This connection, together with the rich properties of the Lov´ asz theta function (such as multiplicativity), yields lower bounds in a uniform, modular way. Another of our examples illustrates the use of graph entropy to lower bound χ(Gf ), and sheds new light on the information-theoretic techniques of [3,4]. En route, we also show that our method is strictly more powerful than the classical fooling
Data Loading...
