Local Distributed Decision and Verification

Heger Arfaoui 1, 2
1 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : This thesis lays in the context of distributed computing on networks, and more particularly on the locality aspects that appear in that context. By the systematic study of decision problems, we introduce the complexity classes ULD and UNLD for local decision and verication respectively, and give separation results describing a hierarchy involving other classes of local decision in the literature. These results are accompanied by a classication of several distributed problems based on the hierarchy we introduce. We examine and discuss two key ingredients in local decision and verication: the interpretation function on the outputs, and node identication. In this thesis, we also isolate the aspect of locality by studying it through the prism of the non-signaling model, which, even though not realistic, oers interesting theoretical possibilities, including the derivation of lower bounds for distributed quantum computing without having to manipulate objects of that theory. Finally, by placing ourselves at the extreme limit of locality constraints, we consider the particular class of two-player games in absence of any communication and examine the limits of quantum distributed computing for this class of games.
Complete list of metadatas

Cited literature [76 references]  Display  Hide  Download

https://hal.inria.fr/tel-01274154
Contributor : Laurent Viennot <>
Submitted on : Monday, February 15, 2016 - 2:51:19 PM
Last modification on : Friday, January 4, 2019 - 5:33:21 PM
Long-term archiving on : Saturday, November 12, 2016 - 9:20:59 PM

Identifiers

  • HAL Id : tel-01274154, version 1

Collections

Citation

Heger Arfaoui. Local Distributed Decision and Verification. Networking and Internet Architecture [cs.NI]. Paris Diderot University, 2014. English. ⟨tel-01274154⟩

Share

Metrics

Record views

203

Files downloads

163