Abstrakt. I [12] en privat approximation av en funktion f definieras som en annan funktion F som approximerar f i vanlig mening, men inte avslöja någon information om x annat än vad som kan härledas från f (x). Vi ger den första tvåparts privata approximationen av l2-avståndet med polylogaritmisk kommunikation. Detta löser framför allt den viktigaste öppna frågan om [12]. Vi tittar sedan på den privata nära granne problem där Alice har en frågepunkt i {0, 1} d och Bob en uppsättning n poäng i {0, 1} d, och Alice bör privat lära sig den punkt närmast hennes fråga. Vi förbättrar befintliga protokoll, lösa öppna frågor av [13, 10]. Sedan slappnar vi av problemet genom att definiera den privata approximationen nära grannen problem, vilket kräver att införa en uppfattning om säker beräkning av approximationer för funktioner som returnerar uppsättningar av punkter snarare än värden. För detta problem ger vi flera protokoll med sublinjär kommunikation.
I synnerhet, Indyk och Woodruff REF ger en polylogaritmisk kommunikation approximation för Hamming avstånd och en säker approximation av nära granne sökproblem.
Polylogarithmic private approximations and efficient matching, ECCC
{'venue': 'Electronic Colloquium on Computational Complexity', 'journal': 'Electronic Colloquium on Computational Complexity (ECCC)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}