Show simple item record

dc.contributor.author
Balliu, Alkida
dc.contributor.author
Brandt, Sebastian
dc.contributor.author
Olivetti, Dennis
dc.date.accessioned
2021-02-23T12:47:38Z
dc.date.available
2021-02-11T03:56:05Z
dc.date.available
2021-02-23T12:47:38Z
dc.date.issued
2020
dc.identifier.isbn
978-1-7281-9621-3
en_US
dc.identifier.isbn
978-1-7281-9622-0
en_US
dc.identifier.other
10.1109/FOCS46700.2020.00042
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/468955
dc.description.abstract
Given a graph G=(V, E), an ( α, β )-ruling set is a subset S⊆V such that the distance between any two vertices in S is at least α, and the distance between any vertex in V and the closest vertex in S is at most β . We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a ( 2, β)-ruling set (and hence also any ( α, β )-ruling set with α>2 ) in the LOCAL model of distributed computing, we show the following, where n denotes the number of vertices, Δ the maximum degree, and c is some universal constant independent of NAND Δ . •Any deterministic algorithm requires Ω(min{logΔβloglogΔ, logΔn})rounds, for all β≤cmin{logΔloglogΔ-√, logΔn} . By optimizing Δ, this impliesa deterministic lower bound of Ω(lognβloglogn-√) for all β≤clognloglogn-√3 . •Any randomized algorithm requires Ω(min{logΔβloglogΔ, logΔlogn}) rounds, for allβ≤cmin{logΔloglogΔ-√, logΔlogn} . By optimizing Δ, this implies a randomized lower bound of Ω(loglognβlogloglogn-?√) for all β≤cloglognlogloglogn √3 . For β>1, this improves on the previously best lower bound of Ω(log?n) rounds that follows from the 30-year-old bounds of Linial [FOCS'87] and Naor [J.Disc.Math.'91] (resp. Ω(1) rounds ifβ∈ω(log?n) ). For β=1, i.e. for the problem of computing a maximal independent set (which is nothing else than a (2, 1)-ruling set), our results improve on the previously best lower bound of Ω(log?n) on trees, as our bounds already hold on trees. © 2020 IEEE
en_US
dc.language.iso
en
en_US
dc.publisher
IEEE
en_US
dc.subject
Ruling set
en_US
dc.subject
maximal independent set
en_US
dc.subject
distributed graph algorithms
en_US
dc.subject
lower bounds
en_US
dc.title
Distributed lower bounds for ruling sets
en_US
dc.type
Conference Paper
dc.date.published
2021-01-19
ethz.book.title
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
en_US
ethz.pages.start
365
en_US
ethz.pages.end
376
en_US
ethz.event
61st Annual Symposium on Foundations of Computer Science (FOCS 2020) (virtual)
en_US
ethz.event.location
Durham, NC, USA
en_US
ethz.event.date
November 16-19, 2020
en_US
ethz.notes
Due to the Coronavirus (COVID-19) the conference was conducted virtually.
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
Piscataway, NJ
en_US
ethz.publication.status
published
en_US
ethz.date.deposited
2021-02-11T03:56:11Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-02-23T12:47:54Z
ethz.rosetta.lastUpdated
2022-03-29T05:24:17Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Distributed%20lower%20bounds%20for%20ruling%20sets&rft.date=2020&rft.spage=365&rft.epage=376&rft.au=Balliu,%20Alkida&Brandt,%20Sebastian&Olivetti,%20Dennis&rft.isbn=978-1-7281-9621-3&978-1-7281-9622-0&rft.genre=proceeding&rft_id=info:doi/10.1109/FOCS46700.2020.00042&rft.btitle=2020%20IEEE%2061st%20Annual%20Symposium%20on%20Foundations%20of%20Computer%20Science%20(FOCS)
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record