{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T22:41:39Z","timestamp":1659393699078},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,8,29]],"date-time":"2017-08-29T00:00:00Z","timestamp":1503964800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s00037-017-0161-3","type":"journal-article","created":{"date-parts":[[2017,8,29]],"date-time":"2017-08-29T10:59:27Z","timestamp":1504004367000},"page":"463-509","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Communication with Contextual Uncertainty"],"prefix":"10.1007","volume":"27","author":[{"given":"Badih","family":"Ghazi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pravesh K.","family":"Kothari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,29]]},"reference":[{"key":"161_CR1","doi-asserted-by":"crossref","unstructured":"Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar & D. Sivakumar (2002). Information Theory Methods in Communication Complexity. In 17th Annual IEEE Conference on Computational Complexity, 93\u2013102.","DOI":"10.1109\/CCC.2002.1004344"},{"key":"161_CR2","doi-asserted-by":"crossref","unstructured":"Mohammad Bavarian, Dmitry Gavinsky & Tsuyoshi Ito (2014). On the role of shared randomness in simultaneous communication. In International Colloquium on Automata, Languages, and Programming, 150\u2013162. Springer.","DOI":"10.1007\/978-3-662-43948-7_13"},{"key":"161_CR3","unstructured":"Eric Blais, Joshua Brody & Badih Ghazi (2014). The Information Complexity of Hamming Distance. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 465."},{"issue":"10","key":"161_CR4","doi-asserted-by":"crossref","first-page":"6351","DOI":"10.1109\/TIT.2011.2134067","volume":"57","author":"Andrej Bogdanov","year":"2011","unstructured":"Bogdanov Andrej, Mossel Elchanan (2011) On Extracting Common Random Bits From Correlated Sources. IEEE Transactions on Information Theory 57(10): 6351\u20136355","journal-title":"IEEE Transactions on Information Theory"},{"key":"161_CR5","doi-asserted-by":"crossref","unstructured":"Cl\u00e9ment Louis Canonne, Venkatesan Guruswami, Raghu Meka & Madhu Sudan (2015). Communication with Imperfectly Shared Randomness. In Innovations in Theoretical Computer Science, ITCS, 257\u2013262.","DOI":"10.1145\/2688073.2688099"},{"key":"161_CR6","doi-asserted-by":"crossref","unstructured":"Badih Ghazi, Pritish Kamath & Madhu Sudan (2016). Communication complexity of permutation-invariant functions. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1902\u20131921. SIAM.","DOI":"10.1137\/1.9781611974331.ch134"},{"key":"161_CR7","unstructured":"Badih Ghazi & Madhu Sudan (2017). The Power of Shared Randomness in Uncertain Communication. In International Colloquium on Automata, Languages and Programming (ICALP), 49:1\u201349:14."},{"issue":"2","key":"161_CR8","first-page":"8","volume":"59","author":"Oded Goldreich","year":"2012","unstructured":"Goldreich Oded, Juba Brendan, Sudan Madhu (2012) A theory of goal-oriented communication. J. ACM 59(2): 8","journal-title":"J. ACM"},{"key":"161_CR9","doi-asserted-by":"crossref","unstructured":"Elad Haramaty & Madhu Sudan (2014). Deterministic compression with uncertain priors. In Innovations in Theoretical Computer Science, ITCS, 377\u2013386.","DOI":"10.1145\/2554797.2554832"},{"key":"161_CR10","doi-asserted-by":"crossref","unstructured":"Prahladh Harsha, Rahul Jain, David McAllester & Jaikumar Radhakrishnan (2007). The communication complexity of correlation. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC\u201907), 10\u201323. IEEE.","DOI":"10.1109\/CCC.2007.32"},{"issue":"4","key":"161_CR11","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.ipl.2006.01.014","volume":"99","author":"Wei Huang","year":"2006","unstructured":"Huang Wei, Shi Yaoyun, Zhang Shengyu, Zhu Yufan (2006) The communication complexity of the Hamming distance problem. Information Processing Letters 99(4): 149\u2013153","journal-title":"Information Processing Letters"},{"key":"161_CR12","unstructured":"Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna & Madhu Sudan (2011). Compression without a common prior: an information-theoretic justification for ambiguity in language. In Innovations in Computer Science, ICS, 79\u201386."},{"key":"161_CR13","doi-asserted-by":"crossref","unstructured":"Brendan Juba & Madhu Sudan (2008). Universal semantic communication I. In 40th Annual ACM Symposium on Theory of Computing, 123\u2013132.","DOI":"10.1145\/1374376.1374397"},{"key":"161_CR14","unstructured":"Brendan Juba & Madhu Sudan (2011). Efficient Semantic Communication via Compatible Beliefs. In Innovations in Computer Science, ICS, 22\u201331."},{"key":"161_CR15","unstructured":"Brendan Juba & Ryan Williams (2013). Massive online teaching to bounded learners. In Innovations in Theoretical Computer Science, ITCS, 1\u201310."},{"issue":"1","key":"161_CR16","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s000370050018","volume":"8","author":"Ilan Kremer","year":"1999","unstructured":"Kremer Ilan, Nisan Noam, Dana Ron (1999) On Randomized One-Round Communication Complexity. Computational Complexity 8(1): 21\u201349","journal-title":"Computational Complexity"},{"key":"161_CR17","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz & Noam Nisan (1997). Communication complexity. Cambridge University Press.","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"161_CR18","doi-asserted-by":"crossref","unstructured":"Alan J Laub (2005). Matrix analysis for scientists and engineers. Siam.","DOI":"10.1137\/1.9780898717907"},{"key":"161_CR19","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher & Eli Upfal (2005). Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"161_CR20","unstructured":"Andrew Chi-Chih Yao (1979). Some Complexity Questions Related to Distributive Computing (Preliminary Report). In 11h Annual ACM Symposium on Theory of Computing, 209\u2013213."},{"key":"161_CR21","unstructured":"Andrew Chi-Chin Yao (1977). Probabilistic computations: Toward a unified measure of complexity. In Foundations of Computer Science, 1977., 18th Annual Symposium on, 222\u2013227. IEEE."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-017-0161-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0161-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0161-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T22:11:13Z","timestamp":1659391873000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-017-0161-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,29]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["161"],"URL":"https:\/\/doi.org\/10.1007\/s00037-017-0161-3","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,29]]}}}