Hierarchies in Local Distributed Decision

F. Meyer auf der Heide, K. Swirkot, (2013).

Download
Restricted 524-paper_01.pdf 534.91 KB
Preprint
Abstract
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.
Publishing Year
LibreCat-ID

Cite this

Meyer auf der Heide F, Swirkot K. Hierarchies in Local Distributed Decision. 2013.
Meyer auf der Heide, F., & Swirkot, K. (2013). Hierarchies in Local Distributed Decision. arXiv.
@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} }
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. Hierarchies in Local Distributed Decision. arXiv, 2013.
Main File(s)
File Name
524-paper_01.pdf 534.91 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-15T10:37:07Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar