{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:49:49Z","timestamp":1770752989740,"version":"3.50.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439470","type":"print"},{"value":"9783662439487","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_58","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"701-712","source":"Crossref","is-referenced-by-count":5,"title":["Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound"],"prefix":"10.1007","author":[{"given":"Gillat","family":"Kol","sequence":"first","affiliation":[]},{"given":"Shay","family":"Moran","sequence":"additional","affiliation":[]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[]},{"given":"Amir","family":"Yehudayoff","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-3","key":"58_CR1","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0012-365X(03)00227-9","volume":"273","author":"N. Alon","year":"2003","unstructured":"Alon, N.: Problems and results in extremal combinatorics\u2013i. Discrete Mathematics\u00a0273(1-3), 31\u201353 (2003)","journal-title":"Discrete Mathematics"},{"issue":"1-2","key":"58_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1017\/S0963548307008917","volume":"18","author":"N. Alon","year":"2009","unstructured":"Alon, N.: Perturbed identity matrices have high rank: Proof and applications. Combinatorics, Probability & Computing\u00a018(1-2), 3\u201315 (2009)","journal-title":"Combinatorics, Probability & Computing"},{"key":"58_CR3","doi-asserted-by":"crossref","unstructured":"Beasley, L.B., Laffey, T.J.: Real rank versus nonnegative rank. Linear Algebra and its Applications\u00a0431(12), 2330\u20132335 (2009); Special Issue in honor of Shmuel Friedland","DOI":"10.1016\/j.laa.2009.02.034"},{"key":"58_CR4","doi-asserted-by":"crossref","unstructured":"Braverman, M., Rao, A.: Information equals amortized communication. In: FOCS, pp. 748\u2013757 (2011)","DOI":"10.1109\/FOCS.2011.86"},{"key":"58_CR5","doi-asserted-by":"crossref","unstructured":"Braverman, M.: Interactive information complexity. In: STOC, pp. 505\u2013524 (2012)","DOI":"10.1145\/2213977.2214025"},{"key":"58_CR6","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Shi, Y., Wirth, A., Yao, A.C.-C.: Informational complexity and the direct sum problem for simultaneous message complexity. In: FOCS, pp. 270\u2013278 (2001)","DOI":"10.1109\/SFCS.2001.959901"},{"key":"58_CR7","first-page":"80","volume":"20","author":"D. Gavinsky","year":"2013","unstructured":"Gavinsky, D., Lovett, S.: En route to the log-rank conjecture: New reductions and equivalent formulations. Electronic Colloquium on Computational Complexity (ECCC)\u00a020, 80 (2013)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"58_CR8","doi-asserted-by":"crossref","unstructured":"Jain, R., Klauck, H.: The partition bound for classical communication complexity and query complexity. In: IEEE Conference on Computational Complexity, pp. 247\u2013258 (2010)","DOI":"10.1109\/CCC.2010.31"},{"key":"58_CR9","doi-asserted-by":"crossref","unstructured":"Kerenidis, I., Laplante, S., Lerays, V., Roland, J., Xiao, D.: Lower bounds on information complexity via zero-communication protocols and applications. In: FOCS, pp. 500\u2013509 (2012)","DOI":"10.1109\/FOCS.2012.68"},{"key":"58_CR10","first-page":"46","volume":"21","author":"G. Kol","year":"2014","unstructured":"Kol, G., Moran, S., Shpilka, A., Yehudayoff, A.: Approximate nonnegative rank is equivalent to the smooth rectangle boundy. Electronic Colloquium on Computational Complexity (ECCC)\u00a021, 46 (2014)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"58_CR11","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"issue":"1&2","key":"58_CR12","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0304-3975(95)00005-4","volume":"156","author":"M. Krause","year":"1996","unstructured":"Krause, M.: Geometric arguments yield better bounds for threshold circuits and distributed computing. Theoretical Computer Science\u00a0156(1&2), 99\u2013117 (1996)","journal-title":"Theoretical Computer Science"},{"key":"58_CR13","unstructured":"Troy Lee\u2019s homepage. Some open problems around nonnegative rank (2012), http:\/\/www.research.rutgers.edu\/~troyjlee\/open_problems.pdf"},{"key":"58_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-642-31594-7_52","volume-title":"Automata, Languages, and Programming","author":"S. Laplante","year":"2012","unstructured":"Laplante, S., Lerays, V., Roland, J.: Classical and quantum partition bound and detector inefficiency. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 617\u2013628. Springer, Heidelberg (2012)"},{"key":"58_CR15","unstructured":"Lov\u00e1sz, L.: Communication complexity: A survey. In: Path, Flows, and VLSI-Networks, pp. 235\u2013265 (1990)"},{"key":"58_CR16","doi-asserted-by":"crossref","unstructured":"Lovett, S.: Communication is bounded by root of rank. CoRR, abs\/1306.1877 (2013)","DOI":"10.1145\/2591796.2591799"},{"key":"58_CR17","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Saks, M.E.: Lattices, m\u00f6bius functions and communication complexity. In: FOCS, pp. 81\u201390 (1988)","DOI":"10.1109\/SFCS.1988.21924"},{"key":"58_CR18","doi-asserted-by":"crossref","unstructured":"Linial, N., Shraibman, A.: Lower bounds in communication complexity based on factorization norms. In: STOC, pp. 699\u2013708 (2007)","DOI":"10.1145\/1250790.1250892"},{"key":"58_CR19","doi-asserted-by":"crossref","unstructured":"Lee, T., Shraibman, A.: An approximation algorithm for approximation rank. In: IEEE Conference on Computational Complexity, pp. 351\u2013357 (2009)","DOI":"10.1109\/CCC.2009.25"},{"issue":"4","key":"58_CR20","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1561\/0400000040","volume":"3","author":"T. Lee","year":"2009","unstructured":"Lee, T., Shraibman, A.: Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science\u00a03(4), 263\u2013398 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"58_CR21","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Schmidt, E.M.: Las vegas is better than determinism in vlsi and distributed computing (extended abstract). In: STOC, pp. 330\u2013337 (1982)","DOI":"10.1145\/800070.802208"},{"issue":"2","key":"58_CR22","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I. Newman","year":"1991","unstructured":"Newman, I.: Private vs. common random bits in communication complexity. Information Processing Letters\u00a039(2), 67\u201371 (1991)","journal-title":"Information Processing Letters"},{"issue":"4","key":"58_CR23","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/BF01192527","volume":"15","author":"N. Nisan","year":"1995","unstructured":"Nisan, N., Wigderson, A.: On rank vs. communication complexity. Combinatorica\u00a015(4), 557\u2013565 (1995)","journal-title":"Combinatorica"},{"key":"58_CR24","first-page":"2003","volume":"67","author":"A.A. Razborov","year":"2002","unstructured":"Razborov, A.A.: Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Science, Mathematics\u00a067, 2003 (2002)","journal-title":"Izvestiya of the Russian Academy of Science, Mathematics"},{"issue":"3","key":"58_CR25","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. Journal of Computer and System Sciences\u00a043(3), 441\u2013466 (1991)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_58","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T15:33:40Z","timestamp":1649345620000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}