NDLI: Information theory methods in communication complexity

Content Provider	IEEE Xplore Digital Library
Author	Bar-Yossef, Z. Jayram, T.S. Kumar, R. Sivakumar, D.
Copyright Year	2002
Description	Author affiliation: Div. of Comput. Sci., California Univ., Berkeley, CA, USA (Bar-Yossef, Z.)
Abstract	We use tools and techniques from information theory to study communication complexity problems in the one-way and simultaneous communication models. Our results include: (1) a tight characterization of multi-party one-way communication complexity for product distributions in terms of VC-dimension and shatter coefficients; (2) an equivalence of multi-party one-way and simultaneous communication models for product distributions; (3) a suite of lower bounds for specific functions in the simultaneous communication model, most notably an optimal lower bound for the multi-party set disjointness problem of Alon et al. (1999) and for the generalized addressing function problem of Babai et al. (1996) for arbitrary groups. Methodologically, our main contribution is rendering communication complexity problems in the framework of information theory. This allows us access to the powerful calculus of information theory and the use of fundamental principles such as Fano's inequality and the maximum likelihood estimate principle.
Sponsorship	IEEE Comput. Soc. Tech. Committee on Math. Found. Comput. (TCMF) SIGACT EATCS Centre de Recherches Math., Univ. Montreal Math. Inf. Technol. & Complex Syst. (MITACS)
Starting Page	93
Ending Page	102
File Size	404771
Page Count	10
File Format	PDF
ISBN	0769514685
ISSN	10930159
DOI	10.1109/CCC.2002.1004344
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2002-05-21
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Information theory Complexity theory Distributed computing Protocols Maximum likelihood decoding Maximum likelihood estimation Calculus Upper bound Computer science Very large scale integration
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

A linear lower bound on the unbounded error probabilistic communication complexity

Rectangle size bounds and threshold covers in communication complexity

Low-complexity blind maximum-likelihood detection for SIMO systems with general constellations

Silence-Based Communication

VLSI Implementation of Area-efficient List Sphere Decoder

VLSI Implementation of Area-efficient List Sphere Decoder

Communication-space tradeoffs for unrestricted protocols

A Flexible VLSI Architecture for Extracting Diversity and Spatial Multiplexing Gains in MIMO Channels

Multiparty communication complexity

Information theory methods in communication complexity

Similar Documents

A linear lower bound on the unbounded error probabilistic communication complexity

Rectangle size bounds and threshold covers in communication complexity

Low-complexity blind maximum-likelihood detection for SIMO systems with general constellations

Silence-Based Communication

VLSI Implementation of Area-efficient List Sphere Decoder

VLSI Implementation of Area-efficient List Sphere Decoder

Communication-space tradeoffs for unrestricted protocols

A Flexible VLSI Architecture for Extracting Diversity and Spatial Multiplexing Gains in MIMO Channels

Multiparty communication complexity

Information theory methods in communication complexity