On the complexity of communication complexity

ABSTRACT

We consider the following question: given a two-argument boolean function f, represented as an N x N binary matrix, how hard is it to determine the (deterministic) communication complexity of f? We address two aspects of this question. On the computational side, we prove that, under appropriate cryptographic assumptions (such as the intractability of factoring), the deterministic communication complexity of f is hard to approximate to within some constant. Under stronger (yet arguably reasonable) assumptions, we obtain even stronger hardness results that match the best known approximation. On the analytic side, we present a family of (two-argument) functions for which determining the deterministic communication complexity (or even obtaining non-trivial lower bounds on it) implies proving circuit lower bounds for some related functions. Such connections between circuit complexity and communication complexity were known before (Karchmer &#; Wigderson, 1988) only in the more involved context of relations (search problems) but not in the context of functions (decision problems). This result, in particular, may explain the difficulty of analyzing the communication complexity of certain functions such as the "clique vs. independent-set" family of functions, introduced by Yannakakis (1988).

REFERENCES

• 1: Scott Aaronson , Avi Wigderson, Algebrization: a new barrier in complexity theory, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374481]
• 2: Alfred V. Aho , Jeffrey D. Ullman , Mihalis Yannakakis, On notions of information transfer in VLSI circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.133-139, December 1983 [doi>10.1145/800061.808742]
• 3: Omer Barkol , Yuval Ishai , Enav Weinreb, Communication in the presence of replication, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374472]
• 4: Mikael Goldmann , Johan Håstad, A simple lower bound for monotone clique using a communication game, Information Processing Letters, v.41 n.4, p.221-226, March 18, 1992 [doi>10.1016/0020-0190(92)90184-W]
• 5: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 6: S. Jukna. On graph complexity. Electronic Colloquium on Computational Complexity (ECCC), 2004.
• 7: Valentine Kabanets , Jin-Yi Cai, Circuit minimization problem, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.73-79, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335314]
• 8: Mauricio Karchmer , Avi Wigderson, Monotone circuits for connectivity require super-logarithmic depth, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.539-550, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62265]
• 9: H. Klauck. Rectangle size bounds and threshold covers in communication complexity. In IEEE Conference on Computational Complexity, pages 118--134, 2003.
• 10: E. Kushilevitz, N. Linial, and R. Ostrovsky. The linear-array conjecture in communication complexity is false. Combinatorica, 19(2):241--254, 1999.
• 11: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 12: Satyanarayana V. Lokam, Remarks on Graph Complexity, Proceedings of the 18th Conference on Foundations of Software Technology and Theoretical Computer Science, p.307-318, December 17-19, 1998
• 13: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 14: Kurt Mehlhorn , Erik M. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.330-337, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802208]
• 15: Moni Naor , Omer Reingold, Number-theoretic constructions of efficient pseudo-random functions, Journal of the ACM (JACM), v.51 n.2, p.231-262, March 2004 [doi>10.1145/972639.972643]
• 16: N. Nisan and A. Wigderson. On rank vs. communication complexity. Combinatorica, 15(4):557--565, 1995.
• 17: J. Orlin. Contentment in graph theory: Covering graphs with cliques. In Nederl. Akad. Wet., Proc., pages 406--424, 1977.
• 18: P. Pudlák , V. Rödl , P. Savický, Graph complexity, Acta Informatica, v.25 n.5, p.515-535, June 1988
• 19: R. Raz and B. Spieker. On the "log rank"-conjecture in communication complexity. Combinatorica, 15(4):567--588, 1995.
• 20: Ran Raz , Avi Wigderson, Monotone circuits for matching require linear depth, Journal of the ACM (JACM), v.39 n.3, p.736-744, July 1992 [doi>10.1145/146637.146684]
• 21: Alexander A. Razborov , Steven Rudich, Natural proofs, Journal of Computer and System Sciences, v.55 n.1, p.24-35, Aug. 1997 [doi>10.1006/jcss.1997.1494]
• 22: Ron Roth, Introduction to Coding Theory, Cambridge University Press, New York, NY, 2006
• 23: C. E. Shannon. The synthesis of two terminal switching circuits. Bell System Technical Journal, 28:59--98, 1949.
• 24: M. Yannakakis. Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci., 43(3):441--466, 1991.
• 25: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]

INDEX TERMS

Primary Classification:
  F. Theory of Computation

Additional Classification:
  F. Theory of Computation
  F.0 GENERAL
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Theory

Keywords:
communication complexity, hardness of approximation, lower bounds, protocol tree, pseudo random functions