Please use this identifier to cite or link to this item: https://doi.org/10.4230/LIPIcs.DISC.2017.29
Title: Some lower bounds in dynamic networks with oblivious adversaries
Authors: I. Jahja 
H. Yu 
Y. Zhao 
Keywords: Adaptive adversary
Communication complexity
Dynamic networks
Lower bounds
Oblivious adversary
Issue Date: Oct-2017
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Citation: I. Jahja, H. Yu, Y. Zhao (2017-10). Some lower bounds in dynamic networks with oblivious adversaries. Leibniz International Proceedings in Informatics, LIPIcs 91. ScholarBank@NUS Repository. https://doi.org/10.4230/LIPIcs.DISC.2017.29
Abstract: This paper considers several closely-related problems in synchronous dynamic networks with oblivious adversaries, and proves novel Ω(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 Ω (d) lower bounds. Our novel lower bounds are hence the first nontrivial 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.
Source Title: Leibniz International Proceedings in Informatics, LIPIcs
URI: https://scholarbank.nus.edu.sg/handle/10635/186046
ISBN: 9783959770538
ISSN: 18688969
DOI: 10.4230/LIPIcs.DISC.2017.29
Appears in Collections:Staff Publications
Elements

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
7. oblivious-disc17-technicalreport.pdf609.28 kBAdobe PDF

OPEN

Post-printView/Download

Page view(s)

175
checked on Feb 2, 2023

Download(s)

1
checked on Feb 2, 2023

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.