Number of the records: 1
The hardness of being private
- 1.
SYSNO ASEP 0430344 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve SCOPUS Title The hardness of being private Author(s) Ada, A. (CA)
Chattopadhyay, S. (IN)
Cook, S.A. (CA)
Fontes, L. (CA)
Koucký, Michal (MU-W) RID, SAI, ORCID
Pitassi, T. (CA)Source Title ACM Transactions on Computation Theory. - : Association for Computing Machinery - ISSN 1942-3454
Roč. 6, č. 1 (2014), s. 1Number of pages 24 s. Language eng - English Country US - United States Keywords approximate privacy ; communication complexity ; information theory Subject RIV BA - General Mathematics R&D Projects GAP202/10/0854 GA ČR - Czech Science Foundation (CSF) IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) Institutional support MU-W - RVO:67985840 EID SCOPUS 84897525414 DOI 10.1145/2567671 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2015
Number of the records: 1