{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T06:33:32Z","timestamp":1774679612287,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,5,23]],"date-time":"2016-05-23T00:00:00Z","timestamp":1463961600000},"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":[[2017,3]]},"DOI":"10.1007\/s00037-016-0125-z","type":"journal-article","created":{"date-parts":[[2016,5,24]],"date-time":"2016-05-24T04:09:01Z","timestamp":1464062941000},"page":"147-197","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Information-theoretic approximations of the nonnegative rank"],"prefix":"10.1007","volume":"26","author":[{"given":"G\u00e1bor","family":"Braun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Jain","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Troy","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,23]]},"reference":[{"key":"125_CR1","doi-asserted-by":"crossref","unstructured":"Z. Bar-Yossef, T.S. Jayram, R. Kumar & D. Sivakumar (2004). An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences 68(4), 702\u2013732. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000003001855 .","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"125_CR2","doi-asserted-by":"crossref","unstructured":"B. Barak, M. Braverman, X. Chen & A. Rao (2010). How to compress interactive communication. In 42nd ACM Symposium on Theory of Computing, 67\u201376.","DOI":"10.1145\/1806689.1806701"},{"key":"125_CR3","doi-asserted-by":"crossref","unstructured":"G. Braun & S. Pokutta (2013). Common information and unique disjointness. In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science, 688\u2013697.","DOI":"10.1109\/FOCS.2013.79"},{"key":"125_CR4","doi-asserted-by":"crossref","unstructured":"G. Braun, S. Fiorini, S. Pokutta & D. Steurer (2012). Approximation limits of linear programs (beyond hierarchies). In 53rd IEEE Symposium on Foundations of Computer Science, 480\u2013489. ISBN 978-1-4673-4383-1.","DOI":"10.1109\/FOCS.2012.10"},{"key":"125_CR5","doi-asserted-by":"crossref","unstructured":"G. Braun, S. Pokutta & D. Zink (2015). Inapproximability of combinatorial problems via small LPs and SDPs. In Proceedings of the 47th Annual Symposium on the Theory of Computing, 107\u2013116.","DOI":"10.1145\/2746539.2746550"},{"key":"125_CR6","doi-asserted-by":"crossref","unstructured":"M. Braverman & A. Moitra (2012). An information complexity approach to extended formulations. IEEE Trans. Inf. Theory 60(10), 6058\u20136069.","DOI":"10.1109\/TIT.2014.2347282"},{"key":"125_CR7","doi-asserted-by":"crossref","unstructured":"M. Braverman & A. Rao (2011). Information equals amortized communication. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, 748\u2013757. IEEE.","DOI":"10.1109\/FOCS.2011.86"},{"key":"125_CR8","doi-asserted-by":"crossref","unstructured":"A. Chakrabarti, Y. Shi, A. Wirth & A. Yao (2001). Informational complexity and the direct sum problem for simultaneous message complexity. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, 270\u2013278.","DOI":"10.1109\/SFCS.2001.959901"},{"key":"125_CR9","doi-asserted-by":"crossref","unstructured":"S.O. Chan, J. Lee, P. Raghavendra & D. Steurer (2013). Approximate constraint satisfaction requires large LP relaxations. In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science, 350\u2013359.","DOI":"10.1109\/FOCS.2013.45"},{"key":"125_CR10","unstructured":"T. Cover & J. Thomas (2006). Elements of information theory. Wiley-interscience."},{"key":"125_CR11","doi-asserted-by":"crossref","unstructured":"H. Fawzi & P. Parrilo (2015). Lower bounds on nonnegative rank via nonnegative nuclear norms. Mathematical Programming Series B 153(1), 41\u201366.","DOI":"10.1007\/s10107-014-0837-2"},{"key":"125_CR12","doi-asserted-by":"crossref","unstructured":"S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary & R. de Wolf (2015). Exponential lower bounds for polytopes in combinatorial optimization. Journal of the ACM 62(2).","DOI":"10.1145\/2716307"},{"key":"125_CR13","doi-asserted-by":"crossref","unstructured":"R. Jain, Y. Shi, Z. Wei & S. Zhang (2013). Efficient protocols for generating bipartite classical distributions and quantum states. Proceedings of SODA 2013.","DOI":"10.1109\/TIT.2013.2258372"},{"key":"125_CR14","doi-asserted-by":"crossref","unstructured":"V. Kaibel & S. Weltge (2015). A short proof that the extension complexity of the correlation polytope grows exponentially. Discrete & Computational Geometry 2, 397\u2013401.","DOI":"10.1007\/s00454-014-9655-9"},{"key":"125_CR15","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1137\/S0895480192238482","volume":"8","author":"M. Karchmer","year":"1995","unstructured":"Karchmer M., Kushilevitz E., Nisan N. (1995) Fractional covers and communication complexity. SIAM J. Discrete Math. 8: 76\u201392","journal-title":"SIAM J. Discrete Math."},{"key":"125_CR16","doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz (1975). On the ratio of optimal integral and fractional covers. Discrete Mathematics 13(4), 383\u2013390. ISSN 0012-365X.","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"125_CR17","unstructured":"L. Lov\u00e1sz (1990). Communication complexity: A survey. In B. Korte, L. Lov\u00e1sz, H. Pr\u00f6mel & A. Schrijver, editors, Paths, flows, and VLSI-layout, 235\u2013265. Springer."},{"key":"125_CR18","doi-asserted-by":"crossref","unstructured":"A. Moitra (2016). An almost optimal algorithm for computing non-negative rank. SIAM J. Comput. 45(1), 156\u2013173.","DOI":"10.1137\/140990139"},{"issue":"2","key":"125_CR19","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"A. A. Razborov","year":"1992","unstructured":"Razborov A. A. (1992) On the Distributional Complexity of Disjointness. Theoret. Comput. Sci. 106(2): 385\u2013390","journal-title":"Theoret. Comput. Sci."},{"key":"125_CR20","doi-asserted-by":"crossref","unstructured":"T. Rothvo\u00df (2014). The matching polytope has exponential extension complexity. In Proceedings of the 46th Annual Symposium on the Theory of Computing, 263\u2013272.","DOI":"10.1145\/2591796.2591834"},{"issue":"3","key":"125_CR21","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/070709967","volume":"20","author":"S.A. Vavasis","year":"2009","unstructured":"Vavasis S.A. (2009) On the complexity of nonnegative matrix factorization. SIAM J. Optim. 20(3): 1364\u20131377","journal-title":"SIAM J. Optim."},{"issue":"2","key":"125_CR22","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1137\/0131026","volume":"31","author":"H.S. Witsenhausen","year":"1976","unstructured":"H.S. Witsenhausen (1976) Values and bounds for the common information of two discrete random variables. SIAM J. App. Math. 31(2): 313\u2013333","journal-title":"SIAM J. App. Math."},{"issue":"3","key":"125_CR23","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1137\/S0097539702407345","volume":"32","author":"R. Wolf de","year":"2003","unstructured":"de Wolf R. (2003) Nondeterministic quantum query and communication complexities. SIAM J. Comput. 32(3): 681\u2013699","journal-title":"SIAM J. Comput."},{"issue":"2","key":"125_CR24","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1109\/TIT.1975.1055346","volume":"21","author":"A. Wyner","year":"1975","unstructured":"A. Wyner (1975) The common information of two dependent random variables. IEEE Trans. Inf. Theory 21(2): 163\u2013179","journal-title":"IEEE Trans. Inf. Theory"},{"key":"125_CR25","unstructured":"M. Yannakakis (1988). Expressing combinatorial optimization problems by linear programs (extended abstract). In Proceedings of the 20th Annual Symposium on the Theory of Computing, 223\u2013228."},{"issue":"3","key":"125_CR26","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M. Yannakakis","year":"1991","unstructured":"Yannakakis M. (1991) Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci. 43(3): 441\u2013466","journal-title":"J. Comput. System Sci."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0125-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0125-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0125-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0125-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:01:59Z","timestamp":1558522919000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0125-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,23]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["125"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0125-z","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,23]]}}}