Vi anser att buller komplexiteten i differentially privata mekanismer i inställningen där användaren frågar d linjära frågor f : R n → R icke-adaptivt. Här representeras databasen av en vektor i R n och närheten mellan databaser mäts i 1-metrisk. Vi visar att buller komplexiteten bestäms av två geometriska parametrar i samband med uppsättningen av frågor. Vi använder denna anslutning för att ge snäva övre och nedre gränser på buller komplexitet för alla d ≤ n. Vi visar att för d slumpmässiga linjära frågor av känslighet 1, är det nödvändigt och tillräckligt att lägga till 2-fel
Nyligen gav Hardt och Talwar REF snäva övre och nedre gränser på den mängd buller som behövs för att säkerställa differential integritet för ett visst antal linjära frågor.
On the geometry of differential privacy
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}