Abstract-Vi studerar kraften i interaktivitet i lokal differential integritet. För det första fokuserar vi på skillnaden mellan helt interaktiva och sekventiella interaktiva protokoll. Sekventiellt interaktiva protokoll kan fråga användare adaptivt i följd, men de kan inte återvända till tidigare tillfrågade användare. De allra flesta befintliga lägre gränser för lokal differentiell integritet gäller endast i sekventiellt interaktiva protokoll, och innan detta dokument var det inte känt om fullt interaktiva protokoll var mer kraftfulla. Vi löser den här frågan. För det första klassificerar vi lokalt privata protokoll efter deras sammansättning, den multiplikativa faktorn genom vilken summan av ett protokolls ensidiga sekretessparametrar överskrider dess totala integritetsgaranti. Vi visar sedan hur man effektivt omvandlar alla helt interaktiva kompositionsprotokoll till ett motsvarande i följd interaktivt protokoll med en uppblåsning i prov komplexitet linjär i denna kompositionalitet. Därefter visar vi att vår minskning är snäv genom att ställa ut en familj av problem så att alla sekventiellt interaktiva protokoll kräver denna uppblåsning i prov komplexitet över en helt interaktiv sammansättning protokoll. Vi riktar sedan vår uppmärksamhet mot hypotestestningsproblem. Vi visar att för en stor klass av sammansatta hypotes testningsproblem - som inkluderar alla enkla hypotes testningsproblem som ett specialfall - är en enkel icke-interaktiv test optimal bland klassen av alla (eventuellt helt interaktiva) tester.
Joseph och Al. REF karakteriserade förhållandet mellan urvalskomplexiteten hos helt interaktiva och sekventiellt interaktiva lokala privata protokoll i termer av en parameter som kallas "kompositionalitet", vilket ger de första separationerna mellan fullständig och sekventiell interaktivitet.
The Role of Interactivity in Local Differential Privacy
{'venue': '2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}