preprint
Hierarchies in Local Distributed Decision
Friedhelm
Meyer auf der Heide
author 15523
Kamil
Swirkot
author
63
department
SFB 901
project
SFB 901 - Subprojekt A1
project
SFB 901 - Project Area A
project
We study the complexity theory for the local distributed setting introduced by Korman, Peleg and Fraigniaud. They have defined three complexity classes LD (Local Decision), NLD (Nondeterministic Local Decision) and NLD^#n. The class LD consists of all languages which can be decided with a constant number of communication rounds. The class NLD consists of all languages which can be verified by a nondeterministic algorithm with a constant number of communication rounds. In order to define the nondeterministic classes, they have transferred the notation of nondeterminism into the distributed setting by the use of certificates and verifiers. The class NLD^#n consists of all languages which can be verified by a nondeterministic algorithm where each node has access to an oracle for the number of nodes. They have shown the hierarchy LD subset NLD subset NLD^#n. Our main contributions are strict hierarchies within the classes defined by Korman, Peleg and Fraigniaud. We define additional complexity classes: the class LD(t) consists of all languages which can be decided with at most t communication rounds. The class NLD-O(f) consists of all languages which can be verified by a local verifier such that the size of the certificates that are needed to verify the language are bounded by a function from O(f). Our main results are refined strict hierarchies within these nondeterministic classes.
https://ris.uni-paderborn.de/download/524/1296/524-paper_01.pdf
application/pdf
arXiv2013
eng
1311.7229
Meyer auf der Heide, F., & Swirkot, K. (2013). Hierarchies in Local Distributed Decision. arXiv.
Meyer auf der Heide, Friedhelm, and Kamil Swirkot. “Hierarchies in Local Distributed Decision.” arXiv, 2013.
F. Meyer auf der Heide and K. Swirkot, “Hierarchies in Local Distributed Decision.” arXiv, 2013.
Meyer auf der Heide, Friedhelm, and Kamil Swirkot. <i>Hierarchies in Local Distributed Decision</i>. arXiv, 2013.
Meyer auf der Heide F, Swirkot K. Hierarchies in Local Distributed Decision. 2013.
@article{Meyer auf der Heide_Swirkot_2013, title={Hierarchies in Local Distributed Decision}, publisher={arXiv}, author={Meyer auf der Heide, Friedhelm and Swirkot, Kamil}, year={2013} }
F. Meyer auf der Heide, K. Swirkot, (2013).
5242017-10-17T12:42:34Z2022-01-06T07:01:48Z