1 Search Results for "Jahja, Irvan"


Document
Some Lower Bounds in Dynamic Networks with Oblivious Adversaries

Authors: Irvan Jahja, Haifeng Yu, and Yuda Zhao

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)


Abstract
This paper considers several closely-related problems in synchronous dynamic networks with oblivious adversaries, and proves novel Omega(d + poly(m)) lower bounds on their time complexity (in rounds). Here d is the dynamic diameter of the dynamic network and m is the total number of nodes. Before this work, the only known lower bounds on these problems under oblivious adversaries were the trivial Omega(d) lower bounds. Our novel lower bounds are hence the first non-trivial lower bounds and also the first lower bounds with a poly(m) term. Our proof relies on a novel reduction from a certain two-party communication complexity problem. Our central proof technique is unique in the sense that we consider the communication complexity with a special leaker. The leaker helps Alice and Bob in the two-party problem, by disclosing to Alice and Bob certain "non-critical" information about the problem instance that they are solving.

Cite as

Irvan Jahja, Haifeng Yu, and Yuda Zhao. Some Lower Bounds in Dynamic Networks with Oblivious Adversaries. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 29:1-29:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{jahja_et_al:LIPIcs.DISC.2017.29,
  author =	{Jahja, Irvan and Yu, Haifeng and Zhao, Yuda},
  title =	{{Some Lower Bounds in Dynamic Networks with Oblivious Adversaries}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.29},
  URN =		{urn:nbn:de:0030-drops-79690},
  doi =		{10.4230/LIPIcs.DISC.2017.29},
  annote =	{Keywords: dynamic networks, oblivious adversary, adaptive adversary, lower bounds, communication complexity}
}
  • Refine by Author
  • 1 Jahja, Irvan
  • 1 Yu, Haifeng
  • 1 Zhao, Yuda

  • Refine by Classification

  • Refine by Keyword
  • 1 adaptive adversary
  • 1 communication complexity
  • 1 dynamic networks
  • 1 lower bounds
  • 1 oblivious adversary

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail