The DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
Informational complexity and the direct sum problem for simultaneous message complexity
Abstract
Given m copies of the same problem, does it take m times the amount of resources to solve these m problems? This is the direct sum problem, a fundamental question that has been studied in many computational models. We study this question in the simultaneous message (SM) model of communication introduced by A.C. Yao (1979). The equality problem for n-bit strings is well known to have SM complexity /spl Theta/(/spl radic/n). We prove that solving m copies of the problem has complexity /spl Omega/(m/spl radic/n); the best lower bound provable using previously known techniques is /spl Omega/(/spl radic/(mn)). We also prove similar lower bounds on certain Boolean combinations of multiple copies of the equality function. These results can be generalized to a broader class of functions. We introduce a new notion of informational complexity which is related to SM complexity and has nice direct sum properties. This notion is used as a tool to prove the above results; it appears to be quite powerful and may be of independent interest.
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
(2005) · Complexity Theory · doi:10.1007/3-540-27477-4_15 · Cited by 1,629
Some complexity questions related to distributive computing(Preliminary Report)
Yao, A. C.-C. (1979) · Proceedings of the eleventh annual ACM symposium on Theory of computing - STOC '79 · doi:10.1145/800135.804414 · Cited by 1,042
Self-citationRandomized simultaneous messages: solution of a problem of Yao in communication complexity
Babai, L., & Kimmel, P. G. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.1997.612319 · Cited by 81
Public vs. private coin flips in one round communication games (extended abstract)
Newman, I., & Szegedy, M. (1996) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/237814.238004 · Cited by 72
Communication Complexity in a 3-Computer Model
Ambainis, A. (1996) · Algorithmica · doi:10.1007/bf01955678 · Cited by 59
Cited by
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
Index Coding With Side Information
Bar-Yossef, Z., Birk, Y., Jayram, T. S., & Kol, T. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2103753 · Cited by 498
Quantum proofs for classical theorems
(2011) · Theory of Computing · doi:10.4086/toc.gs.2011.002 · Cited by 41
Metadata
- Authors
- Chakrabarti, A., Shi, Y., Wirth, A., & Yao, A.
- Venue
- Proceedings 42nd IEEE Symposium on Foundations of Computer Science
- Publisher
- IEEE
- Published
- 2001
- Pages
- 270-278
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2114607430
- Cited by
- 255
- References
- 5
- FWCI
- 2.88
- Type
- conference paper
- Language
- en
- Open access
- closed
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
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.