Vi studerar de grundläggande problemen med identitetstester (god passform), och närhetstester (två prov) av distributioner över k element, under differential integritet. Även om problemen har en lång historia i statistik, ändliga urval gränser för dessa problem har först nyligen fastställts. I detta arbete, vi härleder övre och nedre gränser på provet komplexiteten i båda problemen under ε-differentiell integritet. Våra resultat förbättras över de mest kända algoritmerna för identitetstestning, och är de första resultaten för differentialt privat närhetstestning. Våra gränser är tätt upp till en konstant faktor när antalet prover är O(k), en regim som har samlat mycket uppmärksamhet under det senaste årtiondet eftersom det tillåter egendom testning även när endast en bråkdel av domänen observeras. Våra övre gränser erhålls genom att omvandla (och ibland kombinera) de kända icke-privata testalgoritmer till differentialt privata algoritmer. Vi föreslår ett enkelt, men ändå allmänt förfarande baserat på koppling av distributioner, för att fastställa urval komplexitet lägre gränser för differentialt privata algoritmer. * Författarna listas i alfabetisk ordning.
Senare arbete av Acharya et al. REF härledde de övre och nedre gränserna på provet komplexitet för godhet passform och närhet testning under (, δ)-differentiell integritet.
Differentially Private Testing of Identity and Closeness of Discrete Distributions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}