Hellinger volume and number-on-the-forehead communication complexity

Lee, T; Leonardos, N; Saks, M; Wang, F

Hellinger volume and number-on-the-forehead communication complexity

Lee, T

Leonardos, N Saks, M Wang, F

Permalink

Publisher:: Elsevier BV
Publication Type:: Journal Article
Citation:: Journal of Computer and System Sciences, 2016, 82, (6), pp. 1064-1074
Issue Date:: 2016-09-01

Closed Access

	Filename	Description	Size
	1-s2.0-S0022000016000301-main.pdf	Published version	326.6 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Lee, T https://orcid.org/0000-0001-6912-2338
dc.contributor.author	Leonardos, N
dc.contributor.author	Saks, M
dc.contributor.author	Wang, F
dc.date.accessioned	2022-08-01T07:48:56Z
dc.date.available	2022-08-01T07:48:56Z
dc.date.issued	2016-09-01
dc.identifier.citation	Journal of Computer and System Sciences, 2016, 82, (6), pp. 1064-1074
dc.identifier.issn	0022-0000
dc.identifier.issn	1090-2724
dc.identifier.uri	http://hdl.handle.net/10453/159448
dc.description.abstract	Information-theoretic methods are a powerful tool in communication complexity, providing, in particular, elegant and tight lower bounds on disjointness in the number-in-the-hand (NIH) model. In this paper, we study the applicability of information theoretic methods to the multi-party number-on-the-forehead model (NOF). The lower bound on disjointness in the NIH model has two parts: a direct sum theorem and a lower bound on the one-bit AND function using a beautiful connection between Hellinger distance and protocols [4]. Inspired by this connection, we introduce the notion of Hellinger volume which lower bounds the information cost of multi-party NOF protocols. We provide tools for manipulating and proving lower bounds on Hellinger volume, and use these tools to obtain a lower bound on the information complexity of the ANDk function in the NOF setting. Finally, we discuss the difficulties of proving a direct sum theorem for information cost in the NOF model.
dc.language	en
dc.publisher	Elsevier BV
dc.relation.ispartof	Journal of Computer and System Sciences
dc.relation.isbasedon	10.1016/j.jcss.2016.03.005
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0802 Computation Theory and Mathematics, 0805 Distributed Computing, 0806 Information Systems
dc.subject.classification	Computation Theory & Mathematics
dc.title	Hellinger volume and number-on-the-forehead communication complexity
dc.type	Journal Article
utslib.citation.volume	82
utslib.for	0802 Computation Theory and Mathematics
utslib.for	0805 Distributed Computing
utslib.for	0806 Information Systems
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	closed_access	*
dc.date.updated	2022-08-01T07:48:55Z
pubs.issue	6
pubs.publication-status	Published
pubs.volume	82
utslib.citation.issue	6

Abstract:

Information-theoretic methods are a powerful tool in communication complexity, providing, in particular, elegant and tight lower bounds on disjointness in the number-in-the-hand (NIH) model. In this paper, we study the applicability of information theoretic methods to the multi-party number-on-the-forehead model (NOF). The lower bound on disjointness in the NIH model has two parts: a direct sum theorem and a lower bound on the one-bit AND function using a beautiful connection between Hellinger distance and protocols [4]. Inspired by this connection, we introduce the notion of Hellinger volume which lower bounds the information cost of multi-party NOF protocols. We provide tools for manipulating and proving lower bounds on Hellinger volume, and use these tools to obtain a lower bound on the information complexity of the ANDk function in the NOF setting. Finally, we discuss the difficulties of proving a direct sum theorem for information cost in the NOF model.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/159448