{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:34:07Z","timestamp":1742913247678,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319559100"},{"type":"electronic","value":"9783319559117"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-55911-7_38","type":"book-chapter","created":{"date-parts":[[2017,3,20]],"date-time":"2017-03-20T14:23:37Z","timestamp":1490019817000},"page":"529-542","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Mozhgan","family":"Pourmoradnasseri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk Oliver","family":"Theis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,3,21]]},"reference":[{"key":"38_CR1","doi-asserted-by":"crossref","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, New York (2008)"},{"issue":"2","key":"38_CR2","first-page":"127","volume":"3","author":"LB Beasley","year":"2013","unstructured":"Beasley, L.B., Klauck, H., Lee, T., Theis, D.O.: Communication complexity, linear optimization, and lower bounds for the nonnegative rank of matrices (dagstuhl seminar 13082). Dagstuhl Rep. 3(2), 127\u2013143 (2013)","journal-title":"Dagstuhl Rep."},{"key":"38_CR3","series-title":"Cambridge Studies in Advanced Mathematics","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs. Cambridge Studies in Advanced Mathematics, vol. 73, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"},{"key":"38_CR4","unstructured":"Braun, G., Fiorini, S., Pokutta, S.: Average case polyhedral complexity of the maximum stable set problem. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2014, Barcelona, Spain, 4\u20136 September 2014, pp. 515\u2013530 (2014). http:\/\/dx.doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2014.515"},{"key":"38_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1007\/978-3-642-22935-0_40","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"V Dani","year":"2011","unstructured":"Dani, V., Moore, C.: Independent sets in random graphs from the weighted second moment method. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) APPROX\/RANDOM 2011. LNCS, vol. 6845, pp. 472\u2013482. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-22935-0_40"},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"Dawande, M., Keskinocak, P., Swaminathan, J.M., Tayur, S.: On bipartite and multipartite clique problems. J. Algorithms 41(2), 388\u2013403 (2001). http:\/\/dx.doi.org\/10.1006\/jagm.2001.1199","DOI":"10.1006\/jagm.2001.1199"},{"key":"38_CR7","unstructured":"Dawande, M., Keskinocak, P., Tayur, S.: On the biclique problem in bipartite graphs. Carnegie Mellon University (1996). GSIA Working Paper"},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Hromkovi\u010d, J., Schnitger, G.: A comparison of two lower-bound methods for communication complexity. Theoret. Comput. Sci. 168(1), 39\u201351 (1996). http:\/\/dx.doi.org\/10.1016\/S0304-3975(96)00062-X , 19th International Symposium on Mathematical Foundations of Computer Science, Ko\u0161ice (1994)","DOI":"10.1016\/S0304-3975(96)00062-X"},{"issue":"1","key":"38_CR9","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(1), 67\u201383 (2013)","journal-title":"Discrete Math."},{"key":"38_CR10","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: STOC (2012)","DOI":"10.1145\/2213977.2213988"},{"issue":"2","key":"38_CR11","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/2716307","volume":"62","author":"S Fiorini","year":"2015","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., Wolf, R.D.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM (JACM) 62(2), 17 (2015)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"38_CR12","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1017\/S0963548306007711","volume":"16","author":"D Froncek","year":"2007","unstructured":"Froncek, D., Jerebic, J., Klavzar, S., Kov\u00e1r, P.: Strong isometric dimension, biclique coverings, and sperner\u2019s theorem. Comb. Probab. Comput. 16(2), 271\u2013275 (2007). http:\/\/dx.doi.org\/10.1017\/S0963548306007711","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"38_CR13","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s10107-014-0757-1","volume":"153","author":"MX Goemans","year":"2015","unstructured":"Goemans, M.X.: Smallest compact formulation for the permutahedron. Math. Program. 153(1), 5\u201311 (2015)","journal-title":"Math. Program."},{"issue":"2","key":"38_CR14","first-page":"261","volume":"14","author":"H Hajiabolhassan","year":"2012","unstructured":"Hajiabolhassan, H., Moazami, F.: Secure frameproof code through biclique cover. Discrete Math. Theor. Comput. Sci. 14(2), 261\u2013270 (2012). http:\/\/www.dmtcs.org\/dmtcs-ojs\/index.php\/dmtcs\/article\/view\/2131\/4075","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"24","key":"38_CR15","doi-asserted-by":"crossref","first-page":"3626","DOI":"10.1016\/j.disc.2012.08.016","volume":"312","author":"H Hajiabolhassan","year":"2012","unstructured":"Hajiabolhassan, H., Moazami, F.: Some new bounds for cover-free families through biclique covers. Discrete Math. 312(24), 3626\u20133635 (2012)","journal-title":"Discrete Math."},{"issue":"1","key":"38_CR16","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1090\/S0002-9939-2014-12301-X","volume":"143","author":"Z Izhakian","year":"2015","unstructured":"Izhakian, Z., Janson, S., Rhodes, J.: Superboolean rank and the size of the largest triangular submatrix of a random matrix. Proc. Am. Math. Soc. 143(1), 407\u2013418 (2015)","journal-title":"Proc. Am. Math. Soc."},{"key":"38_CR17","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S Janson","year":"2000","unstructured":"Janson, S., \u0141uczak, T., Rucinski, A.: Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York (2000)"},{"key":"38_CR18","unstructured":"Kaibel, V.: Extended formulations in combinatorial optimization. Optima - Math. Optim. Soc. Newsl. 85, 2\u20137 (2011). www.mathopt.org\/Optima-Issues\/optima85.pdf"},{"key":"38_CR19","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Sipser, M.: Maximum matchings in sparse random graphs. In: FOCS, pp. 364\u2013375 (1981)","DOI":"10.1109\/SFCS.1981.21"},{"issue":"2","key":"38_CR20","first-page":"109","volume":"5","author":"H Klauck","year":"2015","unstructured":"Klauck, H., Lee, T., Theis, D.O., Thomas, R.R.: Limitations of convex programming: lower bounds on extended formulations and factorization ranks (dagstuhl seminar 15082). Dagstuhl Rep. 5(2), 109\u2013127 (2015)","journal-title":"Dagstuhl Rep."},{"key":"38_CR21","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"38_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-540-27801-6_8","volume-title":"Combinatorial Pattern Matching","author":"S Lonardi","year":"2004","unstructured":"Lonardi, S., Szpankowski, W., Yang, Q.: Finding biclusters by random projections. In: Sahinalp, S.C., Muthukrishnan, S., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol. 3109, pp. 102\u2013116. Springer, Heidelberg (2004). doi: 10.1007\/978-3-540-27801-6_8"},{"issue":"3","key":"38_CR23","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/j.tcs.2006.09.023","volume":"368","author":"S Lonardi","year":"2006","unstructured":"Lonardi, S., Szpankowski, W., Yang, Q.: Finding biclusters by random projections. Theor. Comput. Sci. 368(3), 217\u2013230 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"38_CR24","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1016\/0022-0000(93)90035-U","volume":"47","author":"L Lov\u00e1s","year":"1993","unstructured":"Lov\u00e1s, L., Saks, M.: Communication complexity and combinatorial lattice theory. J. Comput. Syst. Sci. 47, 322\u2013349 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"38_CR25","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing \u2013 Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2006)","DOI":"10.1017\/CBO9780511813603"},{"key":"38_CR26","doi-asserted-by":"crossref","unstructured":"Park, G., Szpankowski, W.: Analysis of biclusters with applications to gene expression data. In: International Conference on Analysis of Algorithms. DMTCS Proc. AD, vol. 267, p. 274 (2005)","DOI":"10.46298\/dmtcs.3385"},{"key":"38_CR27","doi-asserted-by":"crossref","unstructured":"Roughgarden, T.: Communication complexity (for algorithm designers). arXiv preprint arXiv:1509.06257 (2015)","DOI":"10.1561\/9781680831153"},{"key":"38_CR28","unstructured":"Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)"},{"key":"38_CR29","first-page":"2431","volume":"9","author":"X Sun","year":"2008","unstructured":"Sun, X., Nobel, A.B.: On the size and recovery of submatrices of ones in a random binary matrix. J. Mach. Learn. Res 9, 2431\u20132453 (2008)","journal-title":"J. Mach. Learn. Res"},{"key":"38_CR30","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441\u2013466 (1991). http:\/\/dx.doi.org\/10.1016\/0022-0000(91)90024-Y","DOI":"10.1016\/0022-0000(91)90024-Y"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-55911-7_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,22]],"date-time":"2023-08-22T18:42:53Z","timestamp":1692729773000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-55911-7_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319559100","9783319559117"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-55911-7_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}