{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:11Z","timestamp":1750220951898,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,3,17]],"date-time":"2019-03-17T00:00:00Z","timestamp":1552780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC QCC and ANR grant RDAM"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>\n            We introduce a new information-theoretic measure, which we call\n            <jats:italic>Public Information Complexity<\/jats:italic>\n            (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing\n            <jats:italic>peer-to-peer<\/jats:italic>\n            model and show a number of interesting properties and applications of our new notion: The Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; and an explicit calculation of the zero-error Public Information Complexity of the\n            <jats:italic>k<\/jats:italic>\n            -party,\n            <jats:italic>n<\/jats:italic>\n            -bit Parity function, where a player outputs the bitwise parity of the inputs. The latter result also establishes that the amount of randomness needed by a private protocol that computes this function is \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/3313230","type":"journal-article","created":{"date-parts":[[2019,3,18]],"date-time":"2019-03-18T12:09:30Z","timestamp":1552910970000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Multi-Party Protocols, Information Complexity and Privacy"],"prefix":"10.1145","volume":"11","author":[{"given":"Iordanis","family":"Kerenidis","sequence":"first","affiliation":[{"name":"CNRS and Universit\u00e9 Paris Diderot, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[{"name":"CNRS and Universit\u00e9 Paris Diderot, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florent","family":"Urrutia","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris Diderot, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.265501"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811969"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201915)","volume":"40","author":"Bauer Balthazar","year":"2015","unstructured":"Balthazar Bauer , Shay Moran , and Amir Yehudayoff . 2015 . Internal compression of protocols to entropy . In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201915) , Naveen Garg, Klaus Jansen, Anup Rao, and Jos\u00e9 D. P. Rolim (Eds.) , Vol. 40 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 481--496. Balthazar Bauer, Shay Moran, and Amir Yehudayoff. 2015. Internal compression of protocols to entropy. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201915), Naveen Garg, Klaus Jansen, Anup Rao, and Jos\u00e9 D. P. Rolim (Eds.), Vol. 40. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 481--496."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938517"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.77"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_42"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488628"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767425"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2347282"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0112-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214414"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875561"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS\u201915)","volume":"30","author":"Chattopadhyay Arkadev","year":"2015","unstructured":"Arkadev Chattopadhyay and Sagnik Mukhopadhyay . 2015 . Tribes is hard in the message passing model . In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS\u201915) , Ernst W. Mayr and Nicolas Ollinger (Eds.), LIPIcs , Vol. 30 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 224--237. Arkadev Chattopadhyay and Sagnik Mukhopadhyay. 2015. Tribes is hard in the message passing model. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS\u201915), Ernst W. Mayr and Nicolas Ollinger (Eds.), LIPIcs, Vol. 30. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 224--237."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.73"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_43"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62214"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63514"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792235864"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195408"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791195877"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2967605"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095207"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/090770801"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.27"},{"key":"e_1_2_1_27_1","volume-title":"Electr. Colloq. Comput. Complex. 22","author":"Ganor Anat","year":"2015","unstructured":"Anat Ganor , Gillat Kol , and Ran Raz . 2015 . Exponential separation of communication and external information . Electr. Colloq. Comput. Complex. 22 (2015), 88. Anat Ganor, Gillat Kol, and Ran Raz. 2015. Exponential separation of communication and external information. Electr. Colloq. Comput. Complex. 22 (2015), 88."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746572"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS\u201909)","volume":"3","author":"Gronemeier Andre","year":"2009","unstructured":"Andre Gronemeier . 2009 . Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness . In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS\u201909) , Susanne Albers and Jean-Yves Marion (Eds.), LIPIcs , Vol. 3 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Germany, 505--516. Andre Gronemeier. 2009. Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness. In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS\u201909), Susanne Albers and Jean-Yves Marion (Eds.), LIPIcs, Vol. 3. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Germany, 505--516."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2034824"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699432"},{"volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP\u201903), Jos C","author":"Jain Rahul","key":"e_1_2_1_32_1","unstructured":"Rahul Jain , Jaikumar Radhakrishnan , and Pranab Sen . 2003. A direct sum theorem in communication complexity via message compression . In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP\u201903), Jos C . M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger (Eds.), Lecture Notes in Computer Science, Vol. 2719 . Springer , 300--315. Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. 2003. A direct sum theorem in communication complexity via message compression. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP\u201903), Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger (Eds.), Lecture Notes in Computer Science, Vol. 2719. Springer, 300--315."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_42"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916)","volume":"58","author":"Kerenidis Iordanis","year":"2016","unstructured":"Iordanis Kerenidis , Adi Ros\u00e9n , and Florent Urrutia . 2016 . Multi-party protocols, information complexity and privacy . In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916) , Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier (Eds.), LIPIcs , Vol. 58 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 57:1--57:16. Iordanis Kerenidis, Adi Ros\u00e9n, and Florent Urrutia. 2016. Multi-party protocols, information complexity and privacy. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916), Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier (Eds.), LIPIcs, Vol. 58. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 57:1--57:16."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806702"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897537"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 31st International Symposium on Distributed Computing (DISC\u201917), Andr\u00e9a W. Richa (Ed.), Leibniz International Proceedings in Informatics","volume":"91","author":"Kol Gillat","year":"2017","unstructured":"Gillat Kol , Rotem Oshman , and Dafna Sadeh . 2017 . Interactive compression for multi-party protocol . In Proceedings of the 31st International Symposium on Distributed Computing (DISC\u201917), Andr\u00e9a W. Richa (Ed.), Leibniz International Proceedings in Informatics , Vol. 91 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 31:1--31:15. Gillat Kol, Rotem Oshman, and Dafna Sadeh. 2017. Interactive compression for multi-party protocol. In Proceedings of the 31st International Symposium on Distributed Computing (DISC\u201917), Andr\u00e9a W. Richa (Ed.), Leibniz International Proceedings in Informatics, Vol. 91. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 31:1--31:15."},{"volume-title":"Computer Science\u2014Theory and Applications: Proceedings of the 10th International Computer Science Symposium in Russia (CSR\u201915)","author":"Kozachinskiy Alexander","key":"e_1_2_1_38_1","unstructured":"Alexander Kozachinskiy . 2015. Computer Science\u2014Theory and Applications: Proceedings of the 10th International Computer Science Symposium in Russia (CSR\u201915) . Springer International Publishing , Cham , 296--309. Alexander Kozachinskiy. 2015. Computer Science\u2014Theory and Applications: Proceedings of the 10th International Computer Science Symposium in Russia (CSR\u201915). Springer International Publishing, Cham, 296--309."},{"volume-title":"Communication Complexity","author":"Kushilevitz Eyal","key":"e_1_2_1_39_1","unstructured":"Eyal Kushilevitz and Noam Nisan . 1997. Communication Complexity . Cambridge University Press . Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1577"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1007525"},{"key":"e_1_2_1_43_1","volume-title":"Electr. Colloq. Comput. Complex. 22","author":"Rao Anup","year":"2015","unstructured":"Anup Rao and Makrand Sinha . 2015 . Simplified separation of information and communication . Electr. Colloq. Comput. Complex. 22 (2015), 57. Anup Rao and Makrand Sinha. 2015. Simplified separation of information and communication. Electr. Colloq. Comput. Complex. 22 (2015), 57."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993686"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-003-0175-x"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M109380X"},{"volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914)","author":"David","key":"e_1_2_1_48_1","unstructured":"David P. Woodruff and Qin Zhang. 2014. An optimal lower bound for distinct elements in the message passing model . In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914) , Chandra Chekuri (Ed.). SIAM, 718--733. David P. Woodruff and Qin Zhang. 2014. An optimal lower bound for distinct elements in the message passing model. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914), Chandra Chekuri (Ed.). SIAM, 718--733."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313230","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313230","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:00Z","timestamp":1750204440000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,17]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3313230"],"URL":"https:\/\/doi.org\/10.1145\/3313230","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,3,17]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}