A Hierarchy of Local Decision

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Feuilloley, Laurent
dc.contributor.author Fraigniaud, Pierre
dc.contributor.author Hirvonen, Juho
dc.contributor.editor Ioannis Chatzigiannakis Michael Mitzenmacher, Yuval Rabani
dc.contributor.editor Sangiorgi, Davide
dc.date.accessioned 2017-05-11T08:59:52Z
dc.date.available 2017-05-11T08:59:52Z
dc.date.issued 2016
dc.identifier.citation Feuilloley , L , Fraigniaud , P & Hirvonen , J 2016 , A Hierarchy of Local Decision . in Y R Ioannis Chatzigiannakis Michael Mitzenmacher & D Sangiorgi (eds) , 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) . vol. 55 , 118 , Leibniz International Proceedings in Informatics (LIPIcs) , Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik , Dagstuhl, Germany , pp. 1-15 , International Colloquium on Automata, Languages and Programming , Rome , Italy , 12-15 July . DOI: 10.4230/LIPIcs.ICALP.2016.118 en
dc.identifier.isbn 978-3-95977-013-2
dc.identifier.other PURE UUID: 9ea7e8de-e652-4b30-a3d9-58caf9a4286c
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/a-hierarchy-of-local-decision(9ea7e8de-e652-4b30-a3d9-58caf9a4286c).html
dc.identifier.other PURE LINK: http://www.scopus.com/inward/record.url?scp=85012887441&partnerID=8YFLogxK
dc.identifier.other PURE LINK: http://drops.dagstuhl.de/opus/volltexte/2016/6253
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/11517786/LIPIcs_ICALP_2016_118.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/25734
dc.description.abstract We extend the notion of distributed decision in the framework of distributed network computing, inspired by recent results on so-called distributed graph automata. We show that, by using distributed decision mechanisms based on the interaction between a prover and a disprover, the size of the certificates distributed to the nodes for certifying a given network property can be drastically reduced. For instance, we prove that minimum spanning tree can be certified with O(log n)-bit certificates in n-node graphs, with just one interaction between the prover and the disprover, while it is known that certifying MST requires(log2 n)-bit certificates if only the prover can act. The improvement can even be exponential for some simple graph properties. For instance, it is known that certifying the existence of a nontrivial automorphism requires (n2) bits if only the prover can act. We show that there is a protocol with two interactions between the prover and the disprover enabling to certify nontrivial automorphism with O(log n)- bit certificates. These results are achieved by defining and analysing a local hierarchy of decision which generalizes the classical notions of proof-labelling schemes and locally checkable proofs. en
dc.format.extent 1-15
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
dc.relation.ispartof International Colloquium on Automata, Languages and Programming en
dc.relation.ispartofseries 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) en
dc.relation.ispartofseries Volume 55 en
dc.relation.ispartofseries Leibniz International Proceedings in Informatics (LIPIcs) en
dc.rights openAccess en
dc.subject.other 113 Computer and information sciences en
dc.title A Hierarchy of Local Decision en
dc.type A4 Artikkeli konferenssijulkaisussa fi
dc.description.version Peer reviewed en
dc.contributor.department Université Sorbonne Paris Cité
dc.contributor.department Department of Computer Science
dc.contributor.department Professorship Suomela J.
dc.subject.keyword Distributed Algorithm
dc.subject.keyword Distributed Decision
dc.subject.keyword Distributed Network Computing
dc.subject.keyword Locality
dc.subject.keyword 113 Computer and information sciences
dc.identifier.urn URN:NBN:fi:aalto-201705114118
dc.identifier.doi 10.4230/LIPIcs.ICALP.2016.118
dc.type.version publishedVersion


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account