Abstrakt. Vi utökar begreppet distribuerat beslut inom ramen för distribuerade nätverksdata, inspirerat av de senaste resultaten på så kallad distribuerad grafautomat. Vi visar att genom att använda distribuerade beslutsmekanismer baserade på interaktionen mellan en provtagare och en motbevisare kan storleken på de certifikat som delas ut till noderna för certifiering av en viss nätverksfastighet drastiskt minskas. Till exempel kan vi bevisa att minsta spännträd kan certifieras med O(log n)-bit certifikat i n-node grafer, med bara en interaktion mellan provkroppen och motprovaren, medan det är känt att certifiering MST kräver  och 2 n-bitar certifikat om bara provaren kan agera. Förbättringen kan även vara exponentiell för några enkla grafegenskaper. Det är t.ex. känt att intygandet av förekomsten av en icke-trivial automorfism kräver bitar om bara provtagaren kan agera. Vi visar att det finns ett protokoll med två interaktioner mellan provaren och motprovaren som gör det möjligt att certifiera icke-trivial automorfism med O(log n)-bitars certifikat. Dessa resultat uppnås genom att man definierar och analyserar en lokal beslutshierarki som generaliserar de klassiska begreppen bevismärkningssystem och lokalt kontrollerbara bevis. * De första och andra författarna fick ytterligare stöd från ANR-projektet DISPLEXITY och från INRIA-projektet GANG.
REF visade att en sådan interaktion mellan en provtagare och en motbevisare avsevärt kan minska bevisstorleken.
A hierarchy of local decision
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}