DSpace Repository

Some Lower Bounds in Dynamic Networks with Oblivious Adversaries*

Show simple item record

dc.contributor.author JAHJA, Irvan
dc.contributor.author YU, Haifeng
dc.contributor.author ZHAO, Yuda
dc.date.accessioned 2017-10-10T08:44:40Z
dc.date.available 2017-10-10T08:44:40Z
dc.identifier.uri http://hdl.handle.net/1900.100/6751
dc.description.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 terms of rounds). Here d is the dynamic diameter of the dynamic network andmis 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 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. en_US
dc.relation.ispartofseries TRA7/17 en_US
dc.title Some Lower Bounds in Dynamic Networks with Oblivious Adversaries* en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Browse

My Account