The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
Complexity classes in communication complexity theory
Open accessAbstract
We take a complexity theoretic view of A. C. Yao's theory of communication complexity. A rich structure of natural complexity classes is introduced. Besides providing a more structured approach to the complexity of a variety of concrete problems of interest to VLSI, the main objective is to exploit the analogy between Turing machine (TM) and communication complexity (CC) classes. The latter provide a more amicable environment for the study of questions analogous to the most notorious problems in TM complexity. Implicitly, CC classes corresponding to P, NP, coNP, BPP and PP have previously been considered. Surprisingly, pcc = Npcc ∩ coNPcc is known [AUY]. We develop the definitions of PSPACEcc and of the polynomial time hierarchy in CC. Notions of reducibility are introduced and a natural complete member in each class is found. BPPcc ⊆ Σ2cc ∩ Π2cc [Si2] remains valid. We solve the question that BPPcc ⊉ NPcc by proving an Ω(√n) lower bound for the bounded-error complexity of the coNPcc- complete problem "disjointness". Similar lower bounds follow for essentially any nontrivial monotone graph property. Another consequence is that the deterministically exponentially hard "equality" relation is not NPcc-hard with respect to oracle-protocol reductions. We prove that the distributional complexity of the disjointness problem is O(√n log n) under any product measure on {0, 1}n × {0, 1}n. This points to the difficulty of improving the Ω(√n) lower bound for the B2PP complexity of "disjointness". The variety of counting and probabilistic classes appears to be greater than in the Turing machine versions. Many of the simplest graph problems (undirected reachability, planarity, bipartiteness, 2-CNF-satisfiability) turn out to be PSPACEcc-hard. The main open problem remains the separation of the hierarchy, more specifically, the conjecture that Σ2cc ≠ Π2cc. Another major problem is to show that PSPACEcc and the probabilistic class UPPcc are not comparable.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Kenny, A. (2018) · Carl Strehlow’s 1909 Comparative Heritage Dictionary: An Aranda, German, Loritja and Dieri to English Dictionary with Introductory Essays · doi:10.22459/cschd.08.2018.04 · Cited by 3,216
Stockmeyer, L. J. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90061-x · Cited by 1,293
Chandra, A. K., Kozen, D. C., & Stockmeyer, L. J. (1981) · Journal of the ACM · doi:10.1145/322234.322243 · Cited by 1,221
Trading group theory for randomness
Babai, L. (1985) · Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85 · doi:10.1145/22145.22192 · Cited by 772
Self-citationRelativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
Baker, T., Gill, J., & Solovay, R. (1975) · SIAM Journal on Computing · doi:10.1137/0204037 · Cited by 738
Computational Complexity of Probabilistic Turing Machines
Gill, J. (1977) · SIAM Journal on Computing · doi:10.1137/0206049 · Cited by 689
Probabilistic Methods in Combinatorics
Spencer, J. (1995) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-9078-6_132 · Cited by 588
Separating the polynomial-time hierarchy by oracles
Yao, A. C.-C. (1985) · 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) · doi:10.1109/sfcs.1985.49 · Cited by 548
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
Chor, B., & Goldreich, O. (1988) · SIAM Journal on Computing · doi:10.1137/0217015 · Cited by 544
A complexity theoretic approach to randomness
Sipser, M. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808762 · Cited by 460
Cited by
The Space Complexity of Approximating the Frequency Moments
Alon, N., Matias, Y., & Szegedy, M. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1545 · Cited by 1,140
The space complexity of approximating the frequency moments
Alon, N., Matias, Y., & Szegedy, M. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237823 · Cited by 822
An information statistics approach to data stream and communication complexity
Bar-Yossef, Z., Jayram, T. S., Kumar, R., & Sivakumar, D. (2004) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2003.11.006 · Cited by 606
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
Babai, L., & Moran, S. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90028-1 · Cited by 589
Self-citationQuantum proofs for classical theorems
(2011) · Theory of Computing · doi:10.4086/toc.gs.2011.002 · Cited by 41
Metadata
- Authors
- Babai, L., Frankl, P., & Simon, J.
- Venue
- 27th Annual Symposium on Foundations of Computer Science (sfcs 1986)
- Publisher
- IEEE
- Published
- 1986-10
- Pages
- 337-347
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2120210041
- Cited by
- 307
- References
- 17
- FWCI
- 3.03
- Type
- conference paper
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Complexity classes in communication complexity theory. https://app.cochat.ai/papers/10.1109/sfcs.1986.15
- The paper
- Babai, L., Frankl, P., & Simon, J. (1986). Complexity classes in communication complexity theory. 27th Annual Symposium on Foundations of Computer Science (sfcs 1986). https://doi.org/10.1109/sfcs.1986.15
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.