"Chattopadhyay, S." . "6" . "24"^^ . . "Kushilevitz [1989] initiated the study of information-theoretic privacy within the context of communication complexity. Unfortunately, it has been shown that most interesting functions are not privately computable [Kushilevitz 1989, Brandt and Sandholm 2008]. The unattainability of perfect privacy for many functions motivated the study of approximate privacy. Feigenbaum et al. [2010a, 2010b] define notions of worst-case as well as average-case approximate privacy and present several interesting upper bounds as well as some open problems for further study. In this article, we obtain asymptotically tight bounds on the trade-offs between both the worst-case and average-case approximate privacy of protocols and their communication cost for Vickrey auctions. Further, we relate the notion of average-case approximate privacy to other measures based on information cost of protocols."@en . "The hardness of being private"@en . "1" . . "ACM Transactions on Computation Theory" . "[422B4802498F]" . . . . . "approximate privacy; communication complexity; information theory"@en . . "1"^^ . "The hardness of being private" . "US - Spojen\u00E9 st\u00E1ty americk\u00E9" . "Kouck\u00FD, Michal" . . "RIV/67985840:_____/14:00430344" . . "Fontes, L." . "1942-3454" . . . . . "The hardness of being private"@en . "Pitassi, T." . . "10.1145/2567671" . . . "18782" . . "6"^^ . "I, P(GAP202/10/0854), P(IAA100190902)" . "RIV/67985840:_____/14:00430344!RIV15-GA0-67985840" . "Ada, A." . "Cook, S. A." . "Kushilevitz [1989] initiated the study of information-theoretic privacy within the context of communication complexity. Unfortunately, it has been shown that most interesting functions are not privately computable [Kushilevitz 1989, Brandt and Sandholm 2008]. The unattainability of perfect privacy for many functions motivated the study of approximate privacy. Feigenbaum et al. [2010a, 2010b] define notions of worst-case as well as average-case approximate privacy and present several interesting upper bounds as well as some open problems for further study. In this article, we obtain asymptotically tight bounds on the trade-offs between both the worst-case and average-case approximate privacy of protocols and their communication cost for Vickrey auctions. Further, we relate the notion of average-case approximate privacy to other measures based on information cost of protocols." . "The hardness of being private" .