License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.10
URN: urn:nbn:de:0030-drops-99583
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9958/
Go to the corresponding LIPIcs Volume Portal

Hoover, Kenneth ; Impagliazzo, Russell ; Mihajlin, Ivan ; Smal, Alexander V.

Half-Duplex Communication Complexity

pdf-format:
LIPIcs-ISAAC-2018-10.pdf (0.4 MB)

Abstract

Suppose Alice and Bob are communicating in order to compute some function f, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for f where in each round one player sends a bit and the other one receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkies instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). The motivation for this kind of a communication model comes from the study of the KRW conjecture. We show that for some definitions this non-classical communication model is, in fact, more powerful than the classical one as it allows to compute some functions in a smaller number of rounds. We also prove lower bounds for these models using both combinatorial and information theoretic methods.

BibTeX - Entry

@InProceedings{hoover_et_al:LIPIcs:2018:9958,
  author =	{Kenneth Hoover and Russell Impagliazzo and Ivan Mihajlin and Alexander V. Smal},
  title =	{{Half-Duplex Communication Complexity}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{10:1--10:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9958},
  URN =		{urn:nbn:de:0030-drops-99583},
  doi =		{10.4230/LIPIcs.ISAAC.2018.10},
  annote =	{Keywords: communication complexity, half-duplex channel, information theory}
}

Keywords: communication complexity, half-duplex channel, information theory
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI