Please use this identifier to cite or link to this item: https://doi.org/10.4230/LIPIcs.DISC.2017.29
DC FieldValue
dc.titleSome lower bounds in dynamic networks with oblivious adversaries
dc.contributor.authorI. Jahja
dc.contributor.authorH. Yu
dc.contributor.authorY. Zhao
dc.date.accessioned2021-02-01T07:32:16Z
dc.date.available2021-02-01T07:32:16Z
dc.date.issued2017-10
dc.identifier.citationI. 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
dc.identifier.isbn9783959770538
dc.identifier.issn18688969
dc.identifier.urihttps://scholarbank.nus.edu.sg/handle/10635/186046
dc.description.abstractThis 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.
dc.language.isoen
dc.publisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
dc.sourceScopus
dc.subjectAdaptive adversary
dc.subjectCommunication complexity
dc.subjectDynamic networks
dc.subjectLower bounds
dc.subjectOblivious adversary
dc.typeConference Paper
dc.contributor.departmentDEPARTMENT OF COMPUTER SCIENCE
dc.description.doi10.4230/LIPIcs.DISC.2017.29
dc.description.sourcetitleLeibniz International Proceedings in Informatics, LIPIcs
dc.description.volume91
dc.published.statePublished
dc.grant.idR-252-000-579-112
dc.grant.fundingagencySingapore Ministry of Education
Appears in Collections:Staff Publications
Elements

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

OPEN

Post-printView/Download

Google ScholarTM

Check

Altmetric


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