Vi visar att, ignorera beräkningsbegränsningar, är det möjligt att släppa sekretessbevarande databaser som är användbara för alla frågor över en diskretiserad domän från någon given koncept klass med polynom VC-dimension. Vi visar en ny lägre gräns för att släppa databaser som är användbara för frågor i halvrymd över en kontinuerlig domän. Trots detta ger vi en integritetsbevarande polynom tid algoritm som släpper information användbar för alla halvrymd frågor, för en något avslappnad definition av användbarhet. Inspirerad av inlärningsteori, introducerar vi en ny uppfattning om dataintegritet, som vi kallar distributionsintegritet, och visar att det är strikt starkare än den rådande integritetsbegreppet, differential integritet.
Blum m.fl. REF visar att det är möjligt att släppa syntetiska privata databaser som är användbara för alla frågor över en diskretiserad domän från en konceptklass med polynomisk Vapnik-Chervonenkis dimension.
A learning theory approach to non-interactive database privacy
{'venue': "STOC '08", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}