NDLI: Informational complexity and the direct sum problem for simultaneous message complexity

Content Provider	IEEE Xplore Digital Library
Author	Chakrabarti, A. Yaoyun Shi Wirth, A. Yao, A.
Copyright Year	2001
Description	Author affiliation: Dept. of Comput. Sci., Princeton Univ., NJ, USA (Chakrabarti, A.; Yaoyun Shi; Wirth, A.; Yao, A.)
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.
Sponsorship	IEEE Comput. Soc. Task Force on Cluster Comput
Starting Page	270
Ending Page	278
File Size	245159
Page Count	9
File Format	PDF
ISBN	0769511163
DOI	10.1109/SFCS.2001.959901
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2001-10-14
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Samarium Computer science Complexity theory Protocols Computational modeling National electric code Books
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Informational complexity and the direct sum problem for simultaneous message complexity (2001)

Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity (2001)

New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques

On the complexity of succinct zero-sum games

The history of complexity

A Direct Product Theorem for Discrepancy

A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness

A Tight Bound for Set Disjointness in the Message-Passing Model

A direct sum theorem in communication complexity via message compression

Informational complexity and the direct sum problem for simultaneous message complexity

Similar Documents

Informational complexity and the direct sum problem for simultaneous message complexity (2001)

Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity (2001)

New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques

On the complexity of succinct zero-sum games

The history of complexity

A Direct Product Theorem for Discrepancy

A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness

A Tight Bound for Set Disjointness in the Message-Passing Model

A direct sum theorem in communication complexity via message compression

Informational complexity and the direct sum problem for simultaneous message complexity