{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T10:05:45Z","timestamp":1775729145657,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,2,22]],"date-time":"2016-02-22T00:00:00Z","timestamp":1456099200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"NSF","award":["CMMI-1300144"],"award-info":[{"award-number":["CMMI-1300144"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,11]]},"DOI":"10.1007\/s00453-016-0132-0","type":"journal-article","created":{"date-parts":[[2016,2,22]],"date-time":"2016-02-22T14:46:30Z","timestamp":1456152390000},"page":"597-629","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Common Information and Unique Disjointness"],"prefix":"10.1007","volume":"76","author":[{"given":"G\u00e1bor","family":"Braun","sequence":"first","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,2,22]]},"reference":[{"key":"132_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Ge, R., Kannan, R., Moitra, A.: Computing a nonnegative matrix factorization-provably. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 145\u2013162. ACM (2012)","DOI":"10.1145\/2213977.2213994"},{"key":"132_CR2","doi-asserted-by":"publisher","unstructured":"Avis, D., Tiwary, H.R.: On the extension complexity of combinatorial polytopes. Math. Program. Ser. B 153(1), 95\u2013115 (2015). doi: 10.1007\/s10107-014-0764-2","DOI":"10.1007\/s10107-014-0764-2"},{"key":"132_CR3","doi-asserted-by":"publisher","unstructured":"Bar-Yossef, Z., Jayram, T., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci. 68(4), 702\u2013732 (2004). doi: 10.1016\/j.jcss.2003.11.006","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"132_CR4","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1287\/moor.26.2.193.10561","volume":"26","author":"A Ben-Tal","year":"2001","unstructured":"Ben-Tal, A., Nemirovski, A.: On polyhedral approximations of the second-order cone. Math. Oper. Res. 26, 193\u2013205 (2001). doi: 10.1287\/moor.26.2.193.10561","journal-title":"Math. Oper. Res."},{"key":"132_CR5","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S.: The matching polytope does not admit fully-polynomial size relaxation schemes. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 837\u2013846 (2015)","DOI":"10.1137\/1.9781611973730.57"},{"key":"132_CR6","doi-asserted-by":"publisher","unstructured":"Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res. 40(3), 756\u2013772 (2015). doi: 10.1287\/moor.2014.0694","DOI":"10.1287\/moor.2014.0694"},{"key":"132_CR7","doi-asserted-by":"publisher","unstructured":"Braun, G., Fiorini, S., Pokutta, S.: Average case polyhedral complexity of the maximum stable set problem. Math. Program. (2013). doi: 10.1007\/s10107-016-0989-3","DOI":"10.1007\/s10107-016-0989-3"},{"key":"132_CR8","unstructured":"Braun, G., Jain, R., Lee, T., Pokutta, S.: Information-theoretic approximations of the nonnegative rank. Electron. Colloq. Comput. Complex. (ECCC) 13(158) (2013). http:\/\/eccc.hpi-web.de\/report\/2013\/158\/"},{"key":"132_CR9","doi-asserted-by":"publisher","unstructured":"Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 161\u2013170 (2013). doi: 10.1145\/2488608.2488629","DOI":"10.1145\/2488608.2488629"},{"key":"132_CR10","doi-asserted-by":"publisher","unstructured":"Braverman, M., Garg, A., Pankratov, D., Weinstein, O.: Information lower bounds via self-reducibility. In: 8th International Computer Science Symposium in Russia, CSR 2013, pp. 183\u2013194 (2013). doi: 10.1007\/978-3-642-38536-0_16","DOI":"10.1007\/978-3-642-38536-0_16"},{"key":"132_CR11","doi-asserted-by":"publisher","unstructured":"Braverman, M., Garg, A., Pankratov, D., Weinstein, O.: From information to exact communication. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 151\u2013160 (2013). doi: 10.1145\/2488608.2488628","DOI":"10.1145\/2488608.2488628"},{"key":"132_CR12","doi-asserted-by":"publisher","unstructured":"Chan, S., Lee, J., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. In: IEEE 54th Annual Symposium on Foundations of Computer Science (2013). doi: 10.1109\/FOCS.2013.45","DOI":"10.1109\/FOCS.2013.45"},{"key":"132_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10288-010-0122-z","volume":"8","author":"M Conforti","year":"2010","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR 8, 1\u201348 (2010). doi: 10.1007\/s10288-010-0122-z","journal-title":"4OR"},{"key":"132_CR14","unstructured":"Cover, T., Thomas, J.: Elements of Information Theory. Wiley-interscience, Hoboken, NJ (2006)"},{"key":"132_CR15","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Fiorini, S., Grappe, R., Tiwary, H.R.: Extended formulations, non-negative factorizations and randomized communication protocols. In: Proceedings of the Second International Conference on Combinatorial Optimization (ISCO 2012), pp. 129\u2013140 (2012)","DOI":"10.1007\/978-3-642-32147-4_13"},{"key":"132_CR16","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of STOC 2012 (2012)","DOI":"10.1145\/2213977.2213988"},{"key":"132_CR17","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Rothvo\u00df, T., Tiwary, H.: Extended formulations for polygons. J. Discrete Comput. Geom. 48(3), 658\u2013668 (2012)","DOI":"10.1007\/s00454-012-9421-9"},{"key":"132_CR18","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.disc.2012.09.015","volume":"313","author":"S Fiorini","year":"2013","unstructured":"Fiorini, S., Kaibel, V., Pashkovich, K., Theis, D.O.: Combinatorial bounds on nonnegative rank and extended formulations. Discrete Math. 313, 67\u201383 (2013)","journal-title":"Discrete Math."},{"key":"132_CR19","first-page":"3349","volume":"13","author":"N Gillis","year":"2012","unstructured":"Gillis, N.: Sparse and unique nonnegative matrix factorization through data preprocessing. J. Mach. Learn. Res. 13, 3349\u20133386 (2012)","journal-title":"J. Mach. Learn. Res."},{"key":"132_CR20","unstructured":"Gillis, N., Glineur, F., Theis, D.O.: Personal communication. 2 (2013)"},{"issue":"1","key":"132_CR21","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$1-\\varepsilon $$ 1 - \u03b5 . Acta Math. 182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"132_CR22","doi-asserted-by":"crossref","unstructured":"Jain, R., Shi, Y., Wei, Z., Zhang, S.: Efficient protocols for generating bipartite classical distributions and quantum states. In: Proceedings of SODA 2013 (2013)","DOI":"10.1109\/TIT.2013.2258372"},{"key":"132_CR23","first-page":"2","volume":"85","author":"V Kaibel","year":"2011","unstructured":"Kaibel, V.: Extended formulations in combinatorial optimization. Optima 85, 2\u20137 (2011)","journal-title":"Optima"},{"issue":"I","key":"132_CR24","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1109\/18.61115","volume":"37","author":"J Lin","year":"1991","unstructured":"Lin, J.: Divergence measures based on the shannon entropy. IEEE Trans. Inf. Theory 37(I), 145\u2013151 (1991). doi: 10.1109\/18.61115","journal-title":"IEEE Trans. Inf. Theory"},{"key":"132_CR25","doi-asserted-by":"crossref","unstructured":"Moitra, A.: An almost optimal algorithm for computing nonnegative rank. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 1454\u20131464 (2013)","DOI":"10.1137\/1.9781611973105.104"},{"key":"132_CR26","unstructured":"Pashkovich, K.: Extended formulations for combinatorial polytopes. PhD thesis, Magdeburg Universit\u00e4t (2012)"},{"key":"132_CR27","doi-asserted-by":"crossref","unstructured":"Pokutta, S., Van Vyve, M.: A note on the extension complexity of the knapsack polytope. Oper. Res. Lett. 41(4), 347\u2013350 (2013)","DOI":"10.1016\/j.orl.2013.03.010"},{"issue":"2","key":"132_CR28","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"AA Razborov","year":"1992","unstructured":"Razborov, A.A.: On the distributional complexity of disjointness. Theor. Comput. Sci. 106(2), 385\u2013390 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"132_CR29","unstructured":"Razborov, A.A.: Personal communication (2012)"},{"key":"132_CR30","unstructured":"Rothvo\u00df, T.: Some 0\/1 polytopes need exponential size extended formulations, (2011). arXiv:1105.0036"},{"key":"132_CR31","doi-asserted-by":"publisher","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. In: Proceedings of STOC, pp. 263\u2013272 (2014). doi: 10.1145\/2591796.2591834","DOI":"10.1145\/2591796.2591834"},{"key":"132_CR32","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.jcta.2013.10.004","volume":"122","author":"Y Shitov","year":"2014","unstructured":"Shitov, Y.: An upper bound for nonnegative rank. J. Comb. Theory 122, 126\u2013132 (2014)","journal-title":"J. Comb. Theory"},{"issue":"2","key":"132_CR33","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1137\/0131026","volume":"31","author":"HS Witsenhausen","year":"1976","unstructured":"Witsenhausen, H.S.: Values and bounds for the common information of two discrete random variables. SIAM J. Appl. Math. 31(2), 313\u2013333 (1976)","journal-title":"SIAM J. Appl. Math."},{"key":"132_CR34","doi-asserted-by":"crossref","unstructured":"de Wolf, R.: Nondeterministic quantum query and communication complexities. SIAM J. Comput. 32(3), 681\u2013699 (2003)","DOI":"10.1137\/S0097539702407345"},{"issue":"2","key":"132_CR35","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1109\/TIT.1975.1055346","volume":"21","author":"A Wyner","year":"1975","unstructured":"Wyner, A.: The common information of two dependent random variables. IEEE Trans. Inf. Theory 21(2), 163\u2013179 (1975)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"132_CR36","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs (extended abstract). In: Proceedings of STOC 1988, pp. 223\u2013228 (1988)","DOI":"10.1145\/62212.62232"},{"issue":"3","key":"132_CR37","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M Yannakakis","year":"1991","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441\u2013466 (1991). doi: 10.1016\/0022-0000(91)90024-Y","journal-title":"J. Comput. Syst. Sci."},{"key":"132_CR38","doi-asserted-by":"crossref","unstructured":"Zhang, S.: Quantum strategic game theory. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 39\u201359. ACM (2012)","DOI":"10.1145\/2090236.2090241"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0132-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0132-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0132-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0132-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T21:27:42Z","timestamp":1567632462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0132-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,22]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["132"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0132-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,22]]}}}