{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T04:48:02Z","timestamp":1770958082176,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,7,1]],"date-time":"2007-07-01T00:00:00Z","timestamp":1183248000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2007,7]]},"DOI":"10.1007\/s00493-007-2160-5","type":"journal-article","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T05:21:33Z","timestamp":1211952093000},"page":"439-463","source":"Crossref","is-referenced-by-count":72,"title":["Complexity measures of sign matrices"],"prefix":"10.1007","volume":"27","author":[{"given":"Nati","family":"Linial","sequence":"first","affiliation":[]},{"given":"Shahar","family":"Mendelson","sequence":"additional","affiliation":[]},{"given":"Gideon","family":"Schechtman","sequence":"additional","affiliation":[]},{"given":"Adi","family":"Shraibman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,5,29]]},"reference":[{"key":"2160_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, P. Frankl and V. R\u00f6dl: Geometrical realizations of set systems and probabilistic communication complexity, in Proceedings of the 26th Symposium on Foundations of Computer Science, pages 277\u2013280, IEEE Computer Society Press, 1985.","DOI":"10.1109\/SFCS.1985.30"},{"key":"2160_CR2","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The probabilistic method","author":"N. Alon","year":"2000","unstructured":"N. Alon and J. H. Spencer: The probabilistic method, Wiley, New York, second edition, 2000.","edition":"second edition"},{"key":"2160_CR3","doi-asserted-by":"crossref","unstructured":"R. I. Arriaga and S. Vempala: An algorithmic theory of learning: Robust concepts and random projection, in IEEE Symposium on Foundations of Computer Science, pages 616\u2013623, 1999.","DOI":"10.1109\/SFFCS.1999.814637"},{"key":"2160_CR4","first-page":"385","volume-title":"14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 2001, Proceedings","author":"S. Ben-David","year":"2001","unstructured":"S. Ben-David, N. Eiron and H. U. Simon: Limitations of learning via embeddings in Euclidean half-spaces, in 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 2001, Proceedings, volume 2111, pages 385\u2013401, Springer, Berlin, 2001."},{"key":"2160_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0653-8","volume-title":"Matrix Analysis","author":"R. Bhatia","year":"1997","unstructured":"R. Bhatia: Matrix Analysis, Springer-Verlag, New York, 1997."},{"issue":"2","key":"2160_CR6","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1023\/A:1009715923555","volume":"2","author":"C. J. C. Burges","year":"1998","unstructured":"C. J. C. Burges: A tutorial on support vector machines for pattern recognition, Data Mining and Knowledge Discovery 2(2) (1998), 121\u2013167.","journal-title":"Data Mining and Knowledge Discovery"},{"key":"2160_CR7","unstructured":"J. Forster: A linear lower bound on the unbounded error probabilistic communication complexity, in SCT: Annual Conference on Structure in Complexity Theory, 2001."},{"key":"2160_CR8","doi-asserted-by":"crossref","unstructured":"J. Forster, M. Krause, S. V. Lokam, R. Mubarakzjanov, N. Schmitt and H. U. Simon: Relations between communication complexity, linear arrangements, and computational complexity; in Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, pages 171\u2013182, 2001.","DOI":"10.1007\/3-540-45294-X_15"},{"key":"2160_CR9","first-page":"402","volume-title":"14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 2001, Proceedings","author":"J. Forster","year":"2001","unstructured":"J. Forster, N. Schmitt and H. U. Simon: Estimating the optimal margins of embeddings in Euclidean half spaces, in 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 2001, Proceedings, volume 2111, pages 402\u2013415, Springer, Berlin, 2001."},{"key":"2160_CR10","doi-asserted-by":"crossref","unstructured":"J. Friedman: A proof of alon\u2019s second eigenvalue conjecture, in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 720\u2013724, ACM Press, 2003.","DOI":"10.1145\/780542.780646"},{"key":"2160_CR11","unstructured":"F. John: Extremum problems with inequalities as subsidiary conditions, Studies and assays presented to R. Courant in his 60th birthday, pages 187\u2013204, 1948."},{"key":"2160_CR12","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume-title":"Conference in modern analysis and probability (New Haven, Conn., 1982)","author":"W. B. Johnson","year":"1984","unstructured":"W. B. Johnson and J. Lindenstrauss: Extensions of lipshitz mappings into a Hilbert space, in Conference in modern analysis and probability (New Haven, Conn., 1982), pages 189\u2013206, Amer. Math. Soc., Providence, RI, 1984."},{"issue":"1","key":"2160_CR13","first-page":"223","volume":"8","author":"J. Kahn","year":"1995","unstructured":"J. Kahn, J. Koml\u00f3s and E. Szemer\u00e9di: On the probability that a random \u00b11-matrix is singular, Journal of the American Mathematical Society 8(1) (1995), 223\u2013240.","journal-title":"Journal of the American Mathematical Society"},{"issue":"4","key":"2160_CR14","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/BF02311250","volume":"63","author":"B. Kashin","year":"1998","unstructured":"B. Kashin and A. Razborov: Improved lower bounds on the rigidity of Hadamard matrices, Mathematical Notes 63(4) (1998), 471\u2013475.","journal-title":"Mathematical Notes"},{"key":"2160_CR15","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan: Communication Complexity, Cambride University Press, 1997.","DOI":"10.1017\/CBO9780511574948"},{"key":"2160_CR16","doi-asserted-by":"crossref","unstructured":"S. V. Lokam: Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity, in IEEE Symposium on Foundations of Computer Science, pages 6\u201315, 1995.","DOI":"10.1109\/SFCS.1995.492457"},{"issue":"3","key":"2160_CR17","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lobotzky","year":"1988","unstructured":"A. Lobotzky, R. Phillips and P. Sarnak: Ramanujan graphs, Combinatorica 8(3) (1988), 261\u2013277.","journal-title":"Combinatorica"},{"issue":"4","key":"2160_CR18","first-page":"71","volume":"9","author":"G. A. Margulis","year":"1973","unstructured":"G. A. Margulis: Explicit constructions of expanders, Problemy Peredaci Informacii 9(4) (1973), 71\u201380.","journal-title":"Problemy Peredaci Informacii"},{"issue":"2","key":"2160_CR19","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0012-365X(91)90112-F","volume":"91","author":"A. Nilli","year":"1991","unstructured":"A. Nilli: On the second eigenvalue of a graph, Discrete Math. 91(2) (1991), 207\u2013210.","journal-title":"Discrete Math."},{"key":"2160_CR20","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Wigderson: On rank vs. communication complexity, in IEEE Symposium on Foundations of Computer Science, pages 831\u2013836, 1994.","DOI":"10.1109\/SFCS.1994.365711"},{"key":"2160_CR21","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/0022-0000(86)90046-2","volume":"33","author":"R. Paturi","year":"1986","unstructured":"R. Paturi and J. Simon: Probabilistic communication complexity, Journal of Computer and System Sciences 33 (1986), 106\u2013123.","journal-title":"Journal of Computer and System Sciences"},{"key":"2160_CR22","series-title":"CBMS Regional Conference Series in Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/cbms\/060","volume-title":"Factorization of linear operators and geometry of Banach spaces","author":"G. Pisier","year":"1986","unstructured":"G. Pisier: Factorization of linear operators and geometry of Banach spaces, volume 60 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1986."},{"key":"2160_CR23","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0012-365X(94)00115-Y","volume":"136","author":"P. Pudl\u00e1k","year":"1994","unstructured":"P. Pudl\u00e1k and V. R\u00f6dl: Some combinatorial-algebraic problems from complexity theory, Discrete Mathematics 136 (1994), 253\u2013279.","journal-title":"Discrete Mathematics"},{"issue":"6","key":"2160_CR24","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0020-0190(97)00190-7","volume":"64","author":"M. A. Shokrollahi","year":"1997","unstructured":"M. A. Shokrollahi, D. A. Spielman and V. Stemann: A remark on matrix rigidity, Information Processing Letters 64(6) (1997), 283\u2013285.","journal-title":"Information Processing Letters"},{"key":"2160_CR25","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF02699376","volume":"81","author":"M. Talagrand","year":"1996","unstructured":"M. Talagrand: Concentration of measures and isoperimetric inequalities in product spaces, Publications Mathematiques de l\u2019I.H.E.S. 81 (1996), 73\u2013205.","journal-title":"Publications Mathematiques de l\u2019I.H.E.S."},{"issue":"3","key":"2160_CR26","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1090\/S0894-0347-07-00555-3","volume":"20","author":"T. Tao","year":"2007","unstructured":"T. Tao and V. Vu: On the singularity probability of random Bernoulli matrices, Journal of the American Mathematical Society 20(3) (2007), 603\u2013628.","journal-title":"Journal of the American Mathematical Society"},{"key":"2160_CR27","series-title":"Pitman Monographs and Surveys in Pure and Applied Mathematics","volume-title":"Banach-Mazur distances and finite-dimensional operator ideals","author":"N. Tomczak-Jaegermann","year":"1989","unstructured":"N. Tomczak-Jaegermann: Banach-Mazur distances and finite-dimensional operator ideals, volume 38 of Pitman Monographs and Surveys in Pure and Applied Mathematics, Longman Scientific & Technical, Harlow, 1989."},{"key":"2160_CR28","first-page":"162","volume":"53","author":"L. G. Valiant","year":"1977","unstructured":"L. G. Valiant: Graph-theoretic arguments in low level complexity, in Proc. 6th MFCS, volume 53, pages 162\u2013176. Springer-Verlag LNCS, 1977.","journal-title":"Proc. 6th MFCS"},{"key":"2160_CR29","volume-title":"The Nature of Statistical Learning Theory","author":"V. N. Vanik","year":"1999","unstructured":"V. N. Vanik: The Nature of Statistical Learning Theory, Springer-Verlag, New York, 1999."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-007-2160-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-007-2160-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-007-2160-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T01:32:45Z","timestamp":1559093565000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-007-2160-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,7]]}},"alternative-id":["2160"],"URL":"https:\/\/doi.org\/10.1007\/s00493-007-2160-5","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7]]}}}