{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:29:17Z","timestamp":1787495357197,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2015,1,11]],"date-time":"2015-01-11T00:00:00Z","timestamp":1420934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2015,1,11]]},"DOI":"10.1145\/2688073.2688074","type":"proceedings-article","created":{"date-parts":[[2015,1,12]],"date-time":"2015-01-12T15:42:45Z","timestamp":1421077365000},"page":"113-122","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication"],"prefix":"10.1145","author":[{"given":"Mika","family":"G\u00f6\u00f6s","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Watson","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,1,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490272"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567671"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446950"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.15"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1017"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.05.001"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.77"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488628"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488629"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634126"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_20"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214414"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875561"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90150-V"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_44"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195408"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2%3C99::AID-RSA7%3E3.0.CO;2-6"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a010"},{"key":"e_1_3_2_1_24_1","first-page":"721","volume-title":"Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM)","author":"G\u00f6\u00f6s M.","year":"2014","unstructured":"M. G\u00f6\u00f6s and T. Watson . Communication complexity of set-disjointness for all probabilities . In Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM) , pages 721 -- 736 . Schloss Dagstuhl , 2014 . doi:10.4230\/LIPIcs.APPROX-RANDOM.2014.721. 10.4230\/LIPIcs.APPROX-RANDOM.2014.721 M. G\u00f6\u00f6s and T. Watson. Communication complexity of set-disjointness for all probabilities. In Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM), pages 721--736. Schloss Dagstuhl, 2014. doi:10.4230\/LIPIcs.APPROX-RANDOM.2014.721."},{"key":"e_1_3_2_1_25_1","first-page":"505","volume-title":"Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Gronemeier A.","year":"2009","unstructured":"A. Gronemeier . 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) , pages 505 -- 516 . Schloss Dagstuhl , 2009 . doi:10.4230\/LIPIcs.STACS.2009.1846. 10.4230\/LIPIcs.STACS.2009.1846 A. Gronemeier. 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), pages 505--516. Schloss Dagstuhl, 2009. doi:10.4230\/LIPIcs.STACS.2009.1846."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_45"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536509"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.32"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684418"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.31"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_42"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780640"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007620"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2190632"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214415"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702405620"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806702"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.33"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44465-8_38"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422471"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_76"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405021"},{"key":"e_1_3_2_1_44_1","volume-title":"Communication Complexity","author":"Kushilevitz E.","year":"1997","unstructured":"E. Kushilevitz and N. Nisan . Communication Complexity . Cambridge University Press , 1997 . E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009656"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1786"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000011"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.37"},{"issue":"5","key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF00279952","article-title":"Graph complexity","volume":"25","author":"P. Pudl","year":"1988","unstructured":"P. Pudl ak, V. R\u00f6dl , and P. Savick y . Graph complexity . Acta Informatica , 25 ( 5 ): 515 -- 535 , 1988 . doi:10.1007\/BF00279952. 10.1007\/BF00279952 P. Pudl ak, V. R\u00f6dl, and P. Savick y. Graph complexity. Acta Informatica, 25(5):515--535, 1988. doi:10.1007\/BF00279952.","journal-title":"Acta Informatica"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009378.1009562"},{"key":"e_1_3_2_1_51_1","volume-title":"On rigid matrices. Technical report","author":"Razborov A.","year":"1989","unstructured":"A. Razborov . On rigid matrices. Technical report , Steklov Mathematical Institute , 1989 . In Russian. A. Razborov. On rigid matrices. Technical report, Steklov Mathematical Institute, 1989. In Russian."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798339041"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90022-9"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90020-2"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08353-7_135"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_2_1_58_1","volume-title":"Technical report, arXiv","author":"Wunderlich H.","year":"2012","unstructured":"H. Wunderlich . A note on a problem in communication complexity. Technical report, arXiv , 2012 . arXiv:1205.0903. H. Wunderlich. A note on a problem in communication complexity. Technical report, arXiv, 2012. arXiv:1205.0903."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0021-5"}],"event":{"name":"ITCS'15: Innovations in Theoretical Computer Science","location":"Rehovot Israel","acronym":"ITCS'15","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2688073.2688074","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2688073.2688074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:12:14Z","timestamp":1750212734000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2688073.2688074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,11]]},"references-count":55,"alternative-id":["10.1145\/2688073.2688074","10.1145\/2688073"],"URL":"https:\/\/doi.org\/10.1145\/2688073.2688074","relation":{},"subject":[],"published":{"date-parts":[[2015,1,11]]},"assertion":[{"value":"2015-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}