---
res:
bibo_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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Friedhelm
foaf_name: Meyer auf der Heide, Friedhelm
foaf_surname: Meyer auf der Heide
foaf_workInfoHomepage: http://www.librecat.org/personId=15523
- foaf_Person:
foaf_givenName: Kamil
foaf_name: Swirkot, Kamil
foaf_surname: Swirkot
dct_date: 2013^xs_gYear
dct_language: eng
dct_publisher: arXiv@
dct_title: Hierarchies in Local Distributed Decision@
...