{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T02:11:07Z","timestamp":1767924667150,"version":"3.49.0"},"reference-count":20,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2000,3,1]],"date-time":"2000-03-01T00:00:00Z","timestamp":951868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4886,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2000,3]]},"DOI":"10.1016\/s0304-3975(99)00185-1","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T01:51:05Z","timestamp":1027648265000},"page":"89-107","source":"Crossref","is-referenced-by-count":22,"title":["Some structural properties of low-rank matrices related to computational complexity"],"prefix":"10.1016","volume":"235","author":[{"given":"Bruno","family":"Codenotti","sequence":"first","affiliation":[]},{"given":"Pavel","family":"Pudl\u00e1k","sequence":"additional","affiliation":[]},{"given":"Giovanni","family":"Resta","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(99)00185-1_BIB1","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.37236\/1192","article-title":"Explicit Ramsey graphs and orthonormal labelings","volume":"1","author":"Alon","year":"1994","journal-title":"Electron. J. Combin."},{"key":"10.1016\/S0304-3975(99)00185-1_BIB2","unstructured":"N. Alon, M. Szegedy, Large sets of nearly orthogonal vectors, preprint."},{"key":"10.1016\/S0304-3975(99)00185-1_BIB3","series-title":"Introduction to Matrix Analysis","author":"Bellman","year":"1960"},{"key":"10.1016\/S0304-3975(99)00185-1_BIB4","doi-asserted-by":"crossref","unstructured":"R.A. Brualdi, H.J. Ryser, Combinatorial Matrix Theory, 1991, Cambridge University Press, Cambridge.","DOI":"10.1017\/CBO9781107325708"},{"key":"10.1016\/S0304-3975(99)00185-1_BIB5","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","article-title":"Intersection theorems for systems of sets","volume":"35","author":"Erd\u0151s","year":"1960","journal-title":"J. London Math. Soc."},{"issue":"2","key":"10.1016\/S0304-3975(99)00185-1_BIB6","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF01303207","article-title":"A note on matrix rigidity","volume":"13","author":"Friedman","year":"1993","journal-title":"Combinatorica"},{"key":"10.1016\/S0304-3975(99)00185-1_BIB7","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0012-365X(83)90081-X","article-title":"On finite set-systems whose every intersection is a Kernel of a star","volume":"47","author":"F\u00fcredi","year":"1983","journal-title":"Discr. Math."},{"key":"10.1016\/S0304-3975(99)00185-1_BIB8","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01268140","article-title":"Top-down lower bounds for depth-three circuits","volume":"5","author":"H\u00e5stad","year":"1995","journal-title":"Comput. Complexity"},{"key":"10.1016\/S0304-3975(99)00185-1_BIB9","doi-asserted-by":"crossref","unstructured":"B.S. Kashin, A.A. Razborov, Improved lower bounds on the rigidity of Hadamard matrices, preprint, 1997.","DOI":"10.1007\/BF02311250"},{"issue":"1","key":"10.1016\/S0304-3975(99)00185-1_BIB10","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1002\/(SICI)1097-0118(199610)23:2<185::AID-JGT9>3.0.CO;2-P","article-title":"The rank and size of graphs","volume":"23","author":"Kotlov","year":"1996","journal-title":"J. Graph Theory"},{"issue":"2","key":"10.1016\/S0304-3975(99)00185-1_BIB11","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1137\/0204014","article-title":"Matrix Factorization over GF[2] and Trace-Orthogonal Bases of GF[2n]","volume":"4","author":"Lempel","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(99)00185-1_BIB12","doi-asserted-by":"crossref","unstructured":"N. Nisan, A. Wigderson, On Rank vs Communication Complexity, Proc. 35th IEEE FOCS, 1994, pp. 831\u2013836.","DOI":"10.1109\/SFCS.1994.365711"},{"key":"10.1016\/S0304-3975(99)00185-1_BIB13","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1137\/S0097539794264809","article-title":"Boolean circuits, tensor ranks and communication complexity","volume":"26\/3","author":"Pudl\u00e1k","year":"1997","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(99)00185-1_BIB14","first-page":"354","article-title":"Lower bounds on the monotone complexity of some boolean functions","volume":"31","author":"Razborov","year":"1985","journal-title":"Sov. Math. Dokl."},{"key":"10.1016\/S0304-3975(99)00185-1_BIB15","unstructured":"A.A. Razborov, On rigid matrices, typeset manuscript in Russian, 1989."},{"key":"10.1016\/S0304-3975(99)00185-1_BIB16","doi-asserted-by":"crossref","unstructured":"R. Raz, B. Spiker, On the log-rank conjecture in communication complexity, Proc. 34th IEEE FOCS, 1993, pp. 168\u2013176.","DOI":"10.1109\/SFCS.1993.366870"},{"key":"10.1016\/S0304-3975(99)00185-1_BIB17","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1090\/dimacs\/004\/38","article-title":"Almost orthogonal lines in Ed","volume":"4","author":"Rosenfeld","year":"1991","journal-title":"DIMACS Ser. Discrete Math."},{"issue":"2","key":"10.1016\/S0304-3975(99)00185-1_BIB18","doi-asserted-by":"crossref","first-page":"343","DOI":"10.2140\/pjm.1967.21.343","article-title":"Concerning nonnegative matrices and doubly stochastic matrices","volume":"21","author":"Sinkhorn","year":"1967","journal-title":"Pacific J. Math."},{"key":"10.1016\/S0304-3975(99)00185-1_BIB19","doi-asserted-by":"crossref","unstructured":"L.G. Valiant, Graph-theoretic arguments in low level complexity, Proc. 6th MFCS, Lecture Notes in Mathematics, Vol. 53, Springer, Berlin, 1977, pp. 162\u2013176.","DOI":"10.1007\/3-540-08353-7_135"},{"key":"10.1016\/S0304-3975(99)00185-1_BIB20","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0095-8956(91)90097-4","article-title":"Extremal Graphs with no C4's, C6's or C10's","volume":"52","author":"Wenger","year":"1991","journal-title":"J. Combin. Theory Ser. B"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599001851?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599001851?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,5,14]],"date-time":"2021-05-14T04:23:09Z","timestamp":1620966189000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397599001851"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,3]]}},"alternative-id":["S0304397599001851"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(99)00185-1","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2000,3]]}}}