{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:55Z","timestamp":1750308775993,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,6,1]],"date-time":"2014-06-01T00:00:00Z","timestamp":1401580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100011039","name":"IARPA","doi-asserted-by":"crossref","award":["FA8750-07-0031"],"award-info":[{"award-number":["FA8750-07-0031"]}],"id":[{"id":"10.13039\/100011039","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0751674, 0753492, and 1018557","0331548, 0534052, and 0716223","331548"],"award-info":[{"award-number":["0751674, 0753492, and 1018557","0331548, 0534052, and 0716223","331548"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:p>\n            The proliferation of online sensitive data about individuals and organizations makes concern about the\n            <jats:italic>privacy<\/jats:italic>\n            of these data a top priority. There have been many formulations of privacy and, unfortunately, many negative results about the feasibility of maintaining privacy of sensitive data in realistic networked environments. We formulate communication-complexity-based definitions, both worst case and average case, of a problem\u2019s\n            <jats:italic>privacy-approximation ratio<\/jats:italic>\n            . We use our definitions to investigate the extent to which approximate privacy is achievable in a number of standard problems: the 2\n            <jats:sup>nd<\/jats:sup>\n            -price Vickrey auction, Yao\u2019s millionaires problem, the public-good problem, and the set-theoretic disjointness and intersection problems.\n          <\/jats:p>\n          <jats:p>\n            For both the 2\n            <jats:sup>nd<\/jats:sup>\n            -price Vickrey auction and the millionaires problem, we show that not only is perfect privacy impossible or infeasibly costly to achieve, but even\n            <jats:italic>close approximations<\/jats:italic>\n            of perfect privacy suffer from the same lower bounds. By contrast, if the inputs are drawn uniformly at random from { 0,\u2026, 2\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            -1}, then, for both problems, simple and natural communication protocols have privacy-approximation ratios that are linear in\n            <jats:italic>k<\/jats:italic>\n            (i.e., logarithmic in the size of the input space). We also demonstrate tradeoffs between privacy and communication in a family of auction protocols.\n          <\/jats:p>\n          <jats:p>\n            We show that the privacy-approximation ratio provided by any protocol for the disjointness and intersection problems is necessarily exponential (in\n            <jats:italic>k<\/jats:italic>\n            ). We also use these ratios to argue that one protocol for each of these problems is significantly fairer than the others we consider (in the sense of relative effects on the privacy of the different players).\n          <\/jats:p>","DOI":"10.1145\/2601067","type":"journal-article","created":{"date-parts":[[2014,7,11]],"date-time":"2014-07-11T12:09:41Z","timestamp":1405080581000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximate Privacy"],"prefix":"10.1145","volume":"10","author":[{"given":"Joan","family":"Feigenbaum","sequence":"first","affiliation":[{"name":"Yale University, New Haven, CT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aaron D.","family":"Jaggard","sequence":"additional","affiliation":[{"name":"Rutgers University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Schapira","sequence":"additional","affiliation":[{"name":"Yale University and UC Berkeley, Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.24"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386807"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.265501"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/060671899"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_2_1_6_1","first-page":"1","article-title":"Auctions with severely bounded communication","volume":"28","author":"Blumrosen Liad","year":"2007","unstructured":"Liad Blumrosen , Noam Nisan , and Ilya Segal . 2007 . Auctions with severely bounded communication . J. Artif. Int. Res. 28 , 1 (March 2007), 233--266. DOI: http:\/\/dx.doi.org\/10.1613\/jair.2081 10.1613\/jair.2081 Liad Blumrosen, Noam Nisan, and Ilya Segal. 2007. Auctions with severely bounded communication. J. Artif. Int. Res. 28, 1 (March 2007), 233--266. DOI: http:\/\/dx.doi.org\/10.1613\/jair.2081","journal-title":"J. Artif. Int. Res."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1330332.1330338"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62214"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404004"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.07.008"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/646765.703990"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159900"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807369"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0013-7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/570810.570812"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 16th International Joint Conference on Artifical Intelligence -","volume":"1","author":"Fujishima Yuzo","year":"1999","unstructured":"Yuzo Fujishima , David McAdams , and Yoav Shoham . 1999 . Speeding up ascending-bid auctions . In Proceedings of the 16th International Joint Conference on Artifical Intelligence - Volume 1 (IJCAI\u201999). Morgan Kaufmann, San Francisco, CA, 554--559. Yuzo Fujishima, David McAdams, and Yoav Shoham. 1999. Speeding up ascending-bid auctions. In Proceedings of the 16th International Joint Conference on Artifical Intelligence - Volume 1 (IJCAI\u201999). Morgan Kaufmann, San Francisco, CA, 554--559."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993605"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536464"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2005.07.011"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-005-0032-z"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9285-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380850"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1598780.1598786"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405021"},{"volume-title":"Communication Complexity","author":"Kushilevitz Eyal","key":"e_1_2_1_26_1","unstructured":"Eyal Kushilevitz and Noam Nisan . 1997. Communication Complexity . Cambridge University Press , New York . Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press, New York."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.14"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.40"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/336992.337028"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791195245"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229073"},{"volume-title":"The On-Line Encyclopedia of Integer Sequences.","author":"OIES.","key":"e_1_2_1_32_1","unstructured":"OIES. 2010. The On-Line Encyclopedia of Integer Sequences. Retrieved from http:\/\/oeis.org. OIES. 2010. The On-Line Encyclopedia of Integer Sequences. Retrieved from http:\/\/oeis.org."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580854"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0056-z"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382751"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601067","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2601067","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:39Z","timestamp":1750278159000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601067"}},"subtitle":["Foundations and Quantification"],"short-title":[],"issued":{"date-parts":[[2014,6]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["10.1145\/2601067"],"URL":"https:\/\/doi.org\/10.1145\/2601067","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2014,6]]},"assertion":[{"value":"2012-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}