research-article

On the complexity of communication complexity

Authors:

Eyal Kushilevitz,

Enav WeinrebAuthors Info & Claims

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

Pages 465 - 474

https://doi.org/10.1145/1536414.1536479

Published: 31 May 2009 Publication History

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]

S. Aaronson and A. Wigderson. Algebrization: a new barrier in complexity theory. In Proc. of the 40th ACM Symp. on the Theory of Computing, pages 731--740, 2008.

Digital Library

[2]

A. Aho, J. Ullman, and M. Yannanakakis. On notations of information transfer in vlsi circuits. In Proc. of the 15th ACM Symp. on the Theory of Computing, pages 133--139, 1983.

Digital Library

[3]

O. Barkol, Y. Ishai, and E. Weinreb. Communication in the presence of replication. In STOC, pages 661--670, 2008.

Digital Library

[4]

M. Goldmann and J. Håstad. A simple lower bound for monotone clique using a communication game. Inf. Process. Lett., 41(4):221--226, 1992.

Digital Library

[5]

O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. J. of the ACM, 33(4):792--807, 1986.

Digital Library

[6]

S. Jukna. On graph complexity. Electronic Colloquium on Computational Complexity (ECCC), 2004.

[7]

V. Kabanets and J. Cai. Circuit minimization problem. In STOC, pages 73--79, 2000.

Digital Library

[8]

M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. In Proc. of the 20th ACM Symp. on the Theory of Computing, pages 539--550, 1988.

Digital Library

[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]

E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997.

Digital Library

[12]

S. V. Lokam. Remarks on graph complexity. In FSTTCS, pages 307--318, 1998.

Digital Library

[13]

C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. J. of the ACM, 41(5):960--981, 1994.

Digital Library

[14]

K. Mehlhorn and E. M. Schmidt. Las vegas is better than determinism in VLSI and distributed computing. In Proc. of the 14th ACM Symp. on the Theory of Computing, pages 330--337, 1982.

Digital Library

[15]

M. Naor and O. Reingold. Number-theoretic constructions of efficient pseudo-random functions. J. ACM, 51(2):231--262, 2004.

Digital Library

[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, and P. Savický. Graph complexity. Acta Inf., 25(5):515--535, 1988.

Digital Library

[19]

R. Raz and B. Spieker. On the "log rank"-conjecture in communication complexity. Combinatorica, 15(4):567--588, 1995.

[20]

R. Raz and A. Wigderson. Monotone circuits for matching require linear depth. J. of the ACM, 39:736--744, 1992.

Digital Library

[21]

A. A. Razborov and S. Rudich. Natural proofs. J. Comput. Syst. Sci., 55(1):24--35, 1997.

Digital Library

[22]

R. Roth. Introduction to Coding Theory. Cambridge University Press, New York, NY, USA, 2006.

Digital Library

[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]

A. C. Yao. Some complexity questions related to distributed computing. In Proc. of the 11th ACM Symp. on the Theory of Computing, pages 209--213, 1979.

Digital Library

Cited By

Hrubeš PTalebanfard N(2022)On the Extension Complexity of Polytopes Separating Subsets of the Boolean CubeDiscrete & Computational Geometry10.1007/s00454-022-00419-370:1(268-278)Online publication date: 17-Aug-2022
https://doi.org/10.1007/s00454-022-00419-3
Hirahara SIlango RLoff B(2021)Hardness of constant-round communication complexityProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.31Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.31
Ilango RLoff BOliveira IAceto L(2020)NP-hardness of circuit minimization for multi-output functionsProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.22(1-36)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.22
Show More Cited By

Index Terms

On the complexity of communication complexity
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Property Testing Lower Bounds via Communication Complexity
Selected papers from the 26th Annual IEEE Conference on Computational Complexity (CCC 2011)

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to ...
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity

We prove that an $\omega(\log^4 n)$ lower bound for the three-party number-on-the-forehead (NOF) communication complexity of the set-disjointness function implies an $n^{\omega(1)}$ size lower bound for treelike Lovász-Schrijver systems that refute ...
Communication Complexity of Simultaneous Messages

In the multiparty communication game (CFL game) of Chandra, Furst, and Lipton [ Proceedings of the 15 th Annual ACM Symposium on Theory of Computing , Boston, MA, 1983, pp. 94--99] k players collaboratively evaluate a function f ( x ₀, . . . , ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

May 2009

750 pages

ISBN:9781605585062

DOI:10.1145/1536414

Program Chair:
Michael Mitzenmacher
Harvard University

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '09

Sponsor:

STOC '09: Symposium on Theory of Computing

May 31 - June 2, 2009

MD, Bethesda, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
628
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)4

Reflects downloads up to 22 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hrubeš PTalebanfard N(2022)On the Extension Complexity of Polytopes Separating Subsets of the Boolean CubeDiscrete & Computational Geometry10.1007/s00454-022-00419-370:1(268-278)Online publication date: 17-Aug-2022
https://doi.org/10.1007/s00454-022-00419-3
Hirahara SIlango RLoff B(2021)Hardness of constant-round communication complexityProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.31Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.31
Ilango RLoff BOliveira IAceto L(2020)NP-hardness of circuit minimization for multi-output functionsProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.22(1-36)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.22
Allender E(2016)The Complexity of ComplexityComputability and Complexity10.1007/978-3-319-50062-1_6(79-94)Online publication date: 1-Dec-2016
https://doi.org/10.1007/978-3-319-50062-1_6
Fiorini SMassar SPokutta STiwary Hde Wolf R(2015)Exponential Lower Bounds for Polytopes in Combinatorial OptimizationJournal of the ACM10.1145/271630762:2(1-23)Online publication date: 6-May-2015
https://dl.acm.org/doi/10.1145/2716307
Shigeta MAmano K(2015)Ordered biclique partitions and communication complexity problemsDiscrete Applied Mathematics10.1016/j.dam.2014.10.029184:C(248-252)Online publication date: 31-Mar-2015
https://dl.acm.org/doi/10.1016/j.dam.2014.10.029
Amano K(2014)Some improved bounds on communication complexity via new decomposition of cliquesDiscrete Applied Mathematics10.5555/2747014.2747167166:C(249-254)Online publication date: 31-Mar-2014
https://dl.acm.org/doi/10.5555/2747014.2747167
Amano K(2014)Some improved bounds on communication complexity via new decomposition of cliquesDiscrete Applied Mathematics10.1016/j.dam.2013.09.015166(249-254)Online publication date: Mar-2014
https://doi.org/10.1016/j.dam.2013.09.015
Fiorini SMassar SPokutta STiwary Hde Wolf RKarloff HPitassi T(2012)Linear vs. semidefinite extended formulationsProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2213988(95-106)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2213988
Kushilevitz EWeinreb E(2009)The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection2009 50th Annual IEEE Symposium on Foundations of Computer Science10.1109/FOCS.2009.15(63-72)Online publication date: Oct-2009
https://doi.org/10.1109/FOCS.2009.15

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten