DocumentCode :
2722103
Title :
Privacy, additional information, and communication
Author :
Bar-Yehuda, Reuven ; Chor, Benny ; Kushilevitz, Eyal
Author_Institution :
Dept. of Comput. Sci., Technion-Israel, Haifa, Israel
fYear :
1990
fDate :
8-11 July 1990
Firstpage :
55
Lastpage :
65
Abstract :
Two parties which hold n-b inputs x and y , respectively, wish to cooperate in computing a predetermined function f(x,y). For most functions f, this task cannot be accomplished privately, namely, without revealing some additional information to at least one of the parties. The authors initiate a quantitative study of T(f), the minimum amount of additional information revealed in any computation of f. This quantity is formally defined, and a combinatorial characterization which determines the value T(f) (up to a multiplicative factor of 2) is found. This enables the authors to give tight lower and upper bounds on the amount of additional information required for computing various (explicit and random) functions. It is shown that additional information is a resource which can be traded for communication complexity
Keywords :
computational complexity; data privacy; additional information; combinatorial characterization; communication complexity; explicit functions; predetermined function; privacy; random functions; tight lower bounds; tight upper bounds; Boolean functions; Complexity theory; Computer science; Cost function; Ear; Privacy; Protocols; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
Type :
conf
DOI :
10.1109/SCT.1990.113954
Filename :
113954
Link To Document :
بازگشت