NDLI: A Discrepancy Lower Bound for Information Complexity

Content Provider	Springer Nature Link
Author	Braverman, Mark Weinstein, Omri
Copyright Year	2015
Abstract	This paper provides the first general technique for proving information lower bounds on two-party unbounded-rounds communication problems. We show that the discrepancy lower bound, which applies to randomized communication complexity, also applies to information complexity. More precisely, if the discrepancy of a two-party function f with respect to a distribution $$\mu $$ is $$Disc_\mu f$$ , then any two party randomized protocol computing f must reveal at least $$\Omega (\log (1/Disc_\mu f))$$ bits of information to the participants. As a corollary, we obtain that any two-party protocol for computing a random function on $$\{0,1\}^n\times \{0,1\}^n$$ must reveal $$\Omega (n)$$ bits of information to the participants. In addition, we prove that the discrepancy of the Greater-Than function is $$\Omega (1/\sqrt{n})$$ , which provides an alternative proof to the recent proof of Viola (Proceedings of the twenty-fourth annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, 6–8 Jan 2013, pp 632–651, 2013) of the $$\Omega (\log n)$$ lower bound on the communication complexity of this well-studied function and, combined with our main result, proves the tight $$\Omega (\log n)$$ lower bound on its information complexity. The proof of our main result develops a new simulation procedure that may be of an independent interest. In a followup breakthrough work of Kerenidis et al. (53rd annual IEEE symposium on foundations of computer science, FOCS 2012, New Brunswick, NJ, USA, 20–23 Oct 2012, pp 500–509, 2012), our simulation procedure served as a building block towards a proof that almost all known lower bound techniques for communication complexity (and not just discrepancy) apply to information complexity as well.
Starting Page	846
Ending Page	864
Page Count	19
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	76
Issue Number	3
e-ISSN	14320541
Language	English
Publisher	Springer US
Publisher Date	2015-11-30
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Algorithm Analysis and Problem Complexity Theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

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

Deterministic Discrepancy Minimization

Solving Some Discrepancy Problems in NC

A Lower Bound for Scheduling Mechanisms

Near-Entropy Hotlink Assignments

An Equivariance Theorem with Applications to Renaming

On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis

A Tight Lower Bound for Computing the Diameter of a 3D Convex Polytope

Theory of Evolutionary Computation

Treewidth Lower Bounds with Brambles

A Discrepancy Lower Bound for Information Complexity

Similar Documents

Deterministic Discrepancy Minimization

Solving Some Discrepancy Problems in NC

A Lower Bound for Scheduling Mechanisms

Near-Entropy Hotlink Assignments

An Equivariance Theorem with Applications to Renaming

On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis

A Tight Lower Bound for Computing the Diameter of a 3D Convex Polytope

Theory of Evolutionary Computation

Treewidth Lower Bounds with Brambles

A Discrepancy Lower Bound for Information Complexity