En lokal egendom rekonstruerare för en graf egenskap är en algoritm som, givet orakle tillgång till adjakens lista över en graf som är "nära" att ha egenskapen, ger orakle tillgång till adjakens matris av en "korrigering" av grafen, dvs.. en graf som har egenskapen och är nära den givna grafen. För denna modell uppnår vi lokala fastighetsrekonstruktioner för egenskaperna konnektivitet och k-konnektivitet i oriktade grafer och egenskapen stark konnektivitet i riktade grafer. Längs vägen presenterar vi en metod för att omvandla en lokal rekonstruerare (som fungerar som en "adjakensmatris orakel" för den korrigerade grafen) till en "adjakenslista orakel". Detta gör det möjligt för oss att rekursivt använda vår lokala rekonstruerare för (k − 1)-anslutning för att få en lokal rekonstruerare för k-anslutning. Vi utvidgar också begreppet lokal fastighetsrekonstruktion till parametriserade grafegenskaper (till exempel att ha diameter som mest D för någon parameter D) och kräver att den korrigerade grafen har egenskapen med parametern nära originalet. Vi får en lokal rekonstruerare för egenskapen låg diameter, där om den ursprungliga grafen är nära att ha diameter D, då den korrigerade grafen har diameter ungefär 2D. Vi utnyttjar också ett samband mellan lokal fastighetsrekonstruktion och fastighetstestning, observerat av Brakerski, för att få nya toleranta fastighetstestare för alla ovannämnda egenskaper. Förutom den för konnektivitet, dessa är de första toleranta egendom testare för dessa egenskaper.
Campagna m.fl. REF tillhandahåller en lokal rekonstruator för konnektivitet.
Local reconstructors and tolerant testers for connectivity and diameter
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}