Abstrakt. Med tanke på en riktad graf G = (V, E) och ett heltal k ≥ 1, en k-transitiv-closure-panner (k-TCspanner) av G är en riktad graf H = (V, E H ) som har (1) samma transitive-closure som G och (2) diameter som mest k. Transitive-closure spännare är en vanlig abstraktion för applikationer i åtkomstkontroll, egendom testning och datastrukturer. Vi visar en koppling mellan 2-TC-spanners och lokala monotonicitetsfilter. Ett lokalt monotonicitetsfilter, introducerat av Saks och Seshadhri (SIAM Journal on Computing, 2010), är en randomiserad algoritm som, givet tillgång till ett orakle för en nästan monoton funktion f : {1, 2,..., m} d → R, kan snabbt utvärdera en relaterad funktion g : {1, 2,..., m} d → R som garanteras vara monoton. Dessutom kan filtret implementeras på ett distribuerat sätt. Vi visar att ett effektivt lokalt monotonitetsfilter innebär en sparsam 2-TC-spanner av den riktade hypergriden, vilket ger en ny teknik för att bevisa lägre gränser för lokala monotonicitetsfilter. Vår anslutning är i själva verket mer allmän: ett effektivt lokalt monotonicitetsfilter för funktioner på en delvis beställd uppsättning (poset) innebär en gles 2-TC-spanner av den riktade acykliska grafen som motsvarar poseten. Vi presenterar nästan tighta övre och nedre gränser på storleken på de glesaste 2-TC-spannarna av den riktade hyperkuben och hypergrid. Dessa gränser innebär starkare nedre gränser för lokala monotonicitetsfilter som nästan motsvarar de övre gränserna för Saks och Seshadhri.
Förutom dessa arbeten på övre gränsen för monotonitet rekonstruktion, Bhattacharyya et al. I REF visade sig en lägre gräns för lokal monotonitetsrekonstruktion av Saks och Seshadhri med hjälp av transitiva stängningsnycklar.
Lower bounds for local monotonicity reconstruction from transitive closure spanners
{'venue': 'In RANDOM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}