Egenskapstestare utgör en viktig klass av sublinjära algoritmer. I standardtestmodellen får en algoritm åtkomst till inmatningsfunktionen f : D → R via ett orakle. Med mycket få undantag, alla fastighetstestare som studeras i denna modell förlitar sig på oraklet för att ge funktionsvärden vid alla tillfrågade domänpunkter. I många realistiska situationer kan orakelt dock inte kunna avslöja funktionsvärdena vid vissa domänpunkter på grund av integritetsproblem, eller när en del av värdena raderas av misstag eller av en motståndare. Testare inte lära sig något användbart om egenskapen genom att fråga de raderade punkter. Dessutom kan en testares kunskap göra det möjligt för en motståndare att radera några av värdena för att öka frågekomplexiteten hos testaren godtyckligt eller, i vissa fall, göra testaren helt värdelös. I detta arbete initierar vi en studie av fastighetstestare som är motståndskraftiga mot förekomsten av kontradiktoriskt raderade funktionsvärden. En α-erasure-resilient ε-tester ges parametrar α, ε  på (0, 1), tillsammans med orakle tillgång till en funktion f sådan att som mest en α-fraktion av funktionsvärden har raderats. Testaren vet inte om ett värde raderas förrän den frågar motsvarande domänpunkt. Testaren måste acceptera med stor sannolikhet om det finns ett sätt att tilldela värden till de raderade punkterna så att den resulterande funktionen uppfyller den önskade egenskapen P. Den måste avvisa med stor sannolikhet om, för varje tilldelning av värden till de raderade punkterna, den resulterande funktionen måste ändras i åtminstone en ε-fraktion av de icke-raderade domänpunkter för att uppfylla P. Vi designar radering-resilient egendom testare för en stor klass av egenskaper. För vissa egenskaper är det möjligt att få erosure-resilient testare genom att helt enkelt använda standard testare som en svart låda. Det finns dock mer utmanande egenskaper som alla kända testare förlitar sig på att fråga en specifik punkt. Om denna punkt raderas, går alla dessa testare sönder. Vi ger effektiva erosure-resilient testare för flera viktiga klasser av sådana egenskaper funktioner inklusive monotonitet, Lipschitz egendom, och konvexitet. Slutligen visar vi en separation mellan standard- och raderingskontroll. Speciellt beskriver vi en egenskap som kan ε-testas med O(1/ε) frågor i standardmodellen, medan testa den i radering-resilient modell kräver antal frågor polynom i ingångsstorleken.
För den raderingståliga modellen, förutom separationen mellan den modellen och standardtestmodellen, utformade REF effektiva raderingståliga testare för viktiga egenskaper, såsom monotonitet och konvexitet.
Erasure-Resilient Property Testing
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}