{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:53:56Z","timestamp":1775282036726,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1990,3,1]],"date-time":"1990-03-01T00:00:00Z","timestamp":636249600000},"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":[[1990,3]]},"DOI":"10.1007\/bf02122698","type":"journal-article","created":{"date-parts":[[2005,9,14]],"date-time":"2005-09-14T15:44:43Z","timestamp":1126712683000},"page":"81-93","source":"Crossref","is-referenced-by-count":80,"title":["Applications of matrix methods to the theory of lower bounds in computational complexity"],"prefix":"10.1007","volume":"10","author":[{"given":"A. A.","family":"Razborov","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"N5","key":"BF02122698_CR1","first-page":"1033","volume":"282","author":"A. E. \u0410\u041d\u0414\u0420\u0415\u0415\u0412","year":"1985","unstructured":"A. E. \u0410\u041d\u0414\u0420\u0415\u0415\u0412, \u041e\u0411 \u041e\u0414\u041d\u041e\u041c \u041c\u0415\u0442\u041e\u0414\u0415 \u043f\u041e\u043b\u0423\u0427\u0415\u041d\u0418\u044c \u041d\u0418\u0436\u041d\u0418\u0445 \u041e\u0446\u0415\u041d\u041e\u043a \u0441\u043b\u041e\u0436 \u041d\u041e\u0441\u0442\u0418 \u0418\u041d\u0414\u0418\u0412\u0418\u0414\u0423\u0410\u043b\u044c\u041d \u044b\u0445 \u041c\u041e\u041d\u041e\u0442\u041e\u041d\u041d\u044b\u0445 \u0424\u0423\u041d\u043a\u0446\u0418\u0418 \u2014 \u0414\u0410\u041d \u0441\u0441\u0441\u0420,1985, \u0442. 282, N5, 1033\u20131037. (Engl. transl. in:Sov. Math. Dokl. 31, 530\u2013534.)","journal-title":"\u0414\u0410\u041d \u0441\u0441\u0441\u0420"},{"issue":"1","key":"BF02122698_CR2","first-page":"3","volume":"26","author":"A. E. \u0410\u041d\u0414\u0420\u0415\u0415\u0412","year":"1987","unstructured":"A. E. \u0410\u041d\u0414\u0420\u0415\u0415\u0412, \u041e\u0411 \u041e\u0414\u041d\u041e\u041c \u041c\u0415\u0442\u041e\u0414\u0415 \u043f\u041e\u043b\u0423\u0427\u0415\u041d\u0418\u044c \u0401\u0424\u0424\u0415\u043a\u0442\u0418\u0412\u041d\u044b\u0445 \u041d\u0418\u0436\u041d\u0418\u0445 \u041e\u0446\u0415\u041d\u041e\u043a \u041c\u041e\u041d\u041e\u0442\u041e\u041d\u041d\u041e\u0418 \u0441\u043b\u041e\u0436\u041d\u041e\u0441\u0442\u0418, \u0410\u043b\u0433\u0415\u0411\u0420\u0410 \u0418 \u043b\u041e\u0433\u0418\u043a\u0410,1987, \u0442. 26, 1, \u0441. 3\u201326.","journal-title":"\u0410\u043b\u0433\u0415\u0411\u0420\u0410 \u0418 \u043b\u041e\u0433\u0418\u043a\u0410"},{"issue":"N4","key":"BF02122698_CR3","first-page":"798","volume":"281","author":"\u0410. \u0410. \u0420\u0410\u0436\u0411\u041e\u0420\u041e\u0412","year":"1985","unstructured":"\u0410. \u0410. \u0420\u0410\u0436\u0411\u041e\u0420\u041e\u0412, \u041d\u0418\u0436\u041d\u0418\u0415 \u041e\u0446\u0415\u041d\u043a\u0418 \u041c\u041e\u041d\u041e\u0442\u041e\u041d\u041d\u041e\u0418 \u0441\u043b\u041e\u0436\u041d\u041e\u0441\u0442\u0418 \u041d\u0415\u043a\u041e\u0442\u041e\u0420\u044b\u0445 \u0411\u0423\u043b\u0415\u0412\u044b\u0445 \u0424\u0423\u041d\u043a\u0446\u0418\u0418 \u2014 \u0414\u0410\u041d \u0441\u0441\u0441\u0420,1985, \u0442. 281, N4, \u0441. 798\u2013801. (Engl. transl. in:Sov. Math. Dokl. 31, 354\u2013357.)","journal-title":"\u0414\u0410\u041d \u0441\u0441\u0441\u0420"},{"key":"BF02122698_CR4","first-page":"887","volume":"37","author":"\u0410. \u0410. \u0420\u0410\u0436\u0411\u041e\u0420\u041e\u0412","year":"1985","unstructured":"\u0410. \u0410. \u0420\u0410\u0436\u0411\u041e\u0420\u041e\u0412, \u041d\u0418\u0436\u041d\u0418\u0415 \u041e\u0446\u0415\u041d\u043a\u0418 \u041c\u041e\u041d\u041e\u0442\u041e\u041d\u041d\u041e\u0418 \u0441\u043b\u041e\u0436\u041d\u041e\u0441\u0442\u0418 \u043b\u041e\u0433\u0418\u0427\u0415\u0441 \u043a\u041e\u0433\u041e \u043f\u0415\u0420\u041c\u0410\u041d\u0415\u041d\u0442\u0410 \u2014 \u201c\u041c\u0410\u0442\u0415\u041c. \u0436\u0410\u041c.\u201d,1985, \u0442. 37, \u0412\u044b\u043f. 6, \u0441. 887\u2013900. (Engl. transl. in:Mathem. Notes of the Academy of Sci. of the USSR 37, 485\u2013493.)","journal-title":"\u201c\u041c\u0410\u0442\u0415\u041c. \u0436\u0410\u041c.\u201d"},{"key":"BF02122698_CR5","first-page":"598","volume":"41","author":"\u0410. \u0410. \u0420\u0410\u0436\u0411\u041e\u0420\u041e\u0412","year":"1987","unstructured":"\u0410. \u0410. \u0420\u0410\u0436\u0411\u041e\u0420\u041e\u0412, \u041d\u0418\u0436 \u041d\u0418\u0415 \u041e\u0446\u0415\u041d\u043a\u0418 \u0420\u0410\u0436\u041c\u0415\u0420\u0410 \u0441\u0445 \u0415\u041c \u041e\u0433\u0420\u0410\u041d\u0418\u0427\u0415\u041d\u041d\u041e\u0418 \u0433\u043b\u0423\u0411\u0418\u041d\u044b \u0412 \u043f\u041e\u043b\u041d\u041e\u041c \u0411\u0410\u0436\u0418\u0441\u0415, \u0441\u041e\u0414\u0415\u0420\u0436\u0410\u0429\u0415\u041c \u0424\u0423\u041d\u043a\u0446\u0418\u0423 \u043b\u041e\u0433\u0418\u0427\u0415\u0441\u043a\u041e\u0433\u041e \u0441\u043b\u041e\u0436\u0415\u041d\u0418\u044c \u2014\u041c\u0410\u0442\u0415\u041c. \u0436\u0410\u041c.,1987, \u0442. 41, \u0412\u044b\u043f. 4, \u0441. 598\u2013607. (Engl. transl. in:Mathem. Notes of the Academy of Sci. of the USSR. 41:4, 333\u2013338.)","journal-title":"\u041c\u0410\u0442\u0415\u041c. \u0436\u0410\u041c."},{"key":"BF02122698_CR6","unstructured":"\u0410. \u0410.\u0420\u0410\u0436\u0411\u041e\u0420\u041e\u0412, \u0424\u041e\u0420\u041c\u0423\u043b\u044b \u041e\u0433\u0420\u0410\u041d\u0418\u0427\u0415\u041d\u041d\u041e\u0418 \u0433\u043b\u0423\u0411\u0418\u041d\u044b \u0412 \u0411\u0410\u0436\u0418\u0441\u0415 &, \u2295 \u0418 \u041d\u0415\u043a\u041e\u0442\u041e\u0420\u044b\u0415 \u043a\u041e\u041c\u0411\u0418\u041d\u0410\u0442\u041e\u0420\u041d\u044b\u0415 \u0436\u0410\u0414\u0410\u0427\u0418 \u2014 \u0412 \u0441\u0411. \u00ab\u0412\u041e\u043f\u0420\u041e\u0441\u044b \u043a\u0418\u0411\u0415\u0420\u041d\u0415\u0442\u0418\u043a\u0418. \u0441\u043b\u041e\u0436 \u041d\u041e\u0441\u0442\u044c \u0412\u044b\u0427\u0418\u0441\u043b\u0415\u041d\u0418\u0418 \u0418 \u043f\u0420\u0418\u043a\u043b\u0410\u0414\u041d\u0410\u044c \u041c\u0410\u0442\u0415\u041c\u0410\u0442\u0418\u0427\u0415\u0441\u043a\u0410\u044c \u043b\u041e\u0433 \u0418\u043a\u0410\u00bb, \u041c.:1988, \u0441. 149\u2013166."},{"key":"BF02122698_CR7","unstructured":"\u043a. \u043b.\u0420\u044b\u041d\u043a\u041e\u0412, \u041c\u041e\u0414\u0418\u0424\u0418 \u043a\u0410\u0446\u0418\u044c \u041c\u0415\u0442\u041e\u0414\u0410 \u0412. \u041c. \u0445\u0420\u0410\u043f\u0427\u0415\u041d\u043a\u041e \u0418 \u043f\u0420\u0418\u041c\u0415\u041d\u0415\u041d\u0418\u0415 \u0415\u0415 \u043a \u041e\u0446\u0415\u041d\u043a \u0410\u041c \u0441\u043b\u041e\u0436\u041d\u041e\u0441\u0442\u0418 \u043f-\u0441\u0445\u0415\u041c \u0414\u043b\u044c \u043a\u041e\u0414\u041e\u0412\u044b\u0445 \u0424\u0423\u041d\u043a\u0446\u0418\u0418 \u2014 \u0412 \u0441\u0411. \u00ab\u041c\u0415\u0442\u041e\u0414\u044b \u0414\u0418\u0441\u043a\u0420\u0415\u0442\u041d\u041e\u0433\u041e \u0410\u041d\u0410\u043b\u0418\u0436\u0410 \u0412 \u0442\u0415\u041e\u0420\u0418\u0418 \u0433\u0420\u0410\u0424\u041e\u0412 \u0418 \u0441\u0445\u0415\u041c\u00bb, \u0412\u044b\u043f. 42, \u041d\u041e\u0412\u041e\u0441\u0418\u0411\u0418\u0420\u0441\u043a,1985, \u0441. 91\u201398."},{"key":"BF02122698_CR8","first-page":"35","volume":"9","author":"\u0412. \u041c. \u0445\u0420\u0410\u043f\u0427\u0415\u041d\u043a\u041e","year":"1971","unstructured":"\u0412. \u041c. \u0445\u0420\u0410\u043f\u0427\u0415\u041d\u043a\u041e, \u041e \u0441\u043b\u041e\u0436\u041d\u041e\u0441\u0442\u0418 \u0420\u0415\u0410\u043b\u0418\u0436\u0410\u0446\u0418\u0418 \u043b\u0418\u041d\u0415\u0418\u041d\u041e\u0418 \u0424\u0423\u041d\u043a\u0446\u0418\u0418 \u0412 \u043a\u043b\u0410\u0441\u0441\u0415 \u043f-\u0441\u0445\u0415\u041c,\u041c\u0410\u0442\u0415\u041c. \u0436\u0410\u041c.,1971, \u0442. 9, \u0412\u044b\u043f. 1, \u0441. 35\u201340. (Engl. transl. in:Mathem. Notes of the Academy of Sci. of the USSR 11 (1972), 474\u2013479.)","journal-title":"\u041c\u0410\u0442\u0415\u041c. \u0436\u0410\u041c."},{"key":"BF02122698_CR9","doi-asserted-by":"crossref","unstructured":"A. V.Aho, J. D.Ullman, M.Yannakakis, On Notions of Information Transfer in VLSI Circuits \u2014Proc. 15th ACM STOC,1983, 133\u2013139.","DOI":"10.1145\/800061.808742"},{"issue":"N1","key":"BF02122698_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"N. Alon, R. B. Boppana, The monotone circuit complexity of Boolean functions,Combinatorica,1987, v. 7, N1, 1\u201322.","journal-title":"Combinatorica"},{"key":"BF02122698_CR11","doi-asserted-by":"crossref","unstructured":"L.Babai, P.Frankl, J.Simon, Complexity classes in communication complexity theory,Proc. 27th IEEE FOCS,1986, 337\u2013347.","DOI":"10.1109\/SFCS.1986.15"},{"key":"BF02122698_CR12","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0019-9958(82)90766-5","volume":"52","author":"A. Borodin","year":"1982","unstructured":"A. Borodin, von zur Gathen, J. Hopcroft, Fast parallel matrix and GCD computations,Information and Control,52 (1982), 241\u2013256.","journal-title":"Information and Control"},{"key":"BF02122698_CR13","doi-asserted-by":"crossref","unstructured":"B.Halsenberg, R.Reischuk, On Different Modes of Communication, 1988, 20th ACM STOC. 162\u2013172.","DOI":"10.1145\/62212.62226"},{"key":"BF02122698_CR14","doi-asserted-by":"crossref","unstructured":"M.Karchmer, A.Wigderson, Monotone Circuits for Connectivity Require Super-logarithmic Depth,Proc. 20th ACM STOC,1988, 539\u2013550.","DOI":"10.1145\/62212.62265"},{"issue":"1","key":"BF02122698_CR15","doi-asserted-by":"crossref","first-page":"166","DOI":"10.2307\/2035248","volume":"18","author":"B. Lindstr\u00f6m","year":"1967","unstructured":"B. Lindstr\u00f6m, H. O. Zetterstr\u00f6m, A combinatorial problem in thek-adic number system,Proc. of the Amer. Math. Soc., 1967,18, 1, 166\u2013170.","journal-title":"Proc. of the Amer. Math. Soc."},{"key":"BF02122698_CR16","doi-asserted-by":"crossref","unstructured":"R. J.Lipton, R.Sedgewick, Lower Bounds for VLSI,Proc. 13th ACM STOC,1981, 300\u2013307.","DOI":"10.1145\/800076.802482"},{"key":"BF02122698_CR17","doi-asserted-by":"crossref","unstructured":"K.Mehlhorn, E. M.Schmidt, Las Vegas is better than determinism in VLSI and distributive computing,Proc. 14th ACM STOC,1982, 330\u2013337.","DOI":"10.1145\/800070.802208"},{"key":"BF02122698_CR18","unstructured":"P.Pudlak, V.R\u00f6dl,A combinatorial approach to complexity\u2014unpublished manuscript,1989."},{"key":"BF02122698_CR19","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF00279952","volume":"25","author":"P. Pudlak","year":"1988","unstructured":"P. Pudlak, V. R\u00f6dl, P. Savicky, Graph Complexity,Acta Informatica,25 (1988), 515\u2013535.","journal-title":"Acta Informatica"},{"key":"BF02122698_CR20","first-page":"525","volume-title":"On time-hardware complexity tradeoffs for Boolean functions","author":"P. M. Spira","year":"1971","unstructured":"P. M. Spira, On time-hardware complexity tradeoffs for Boolean functions,Proceedings of 4th Hawaii Symposium on System Sciences,1971, Western Periodicals Company, North Hollywood, 525\u2013527."},{"issue":"1","key":"BF02122698_CR21","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF02122563","volume":"8","author":"\u00e9. Tardos","year":"1988","unstructured":"\u00e9. Tardos, The gap between monotone and non-monotone circuit complexity is exponential,Combinatorica,1988, v. 8,1, 141\u2013142.","journal-title":"Combinatorica"},{"key":"BF02122698_CR22","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0020-0190(83)90011-X","volume":"16","author":"I. Wegeher","year":"1983","unstructured":"I. Wegeher, Relating monotone formula size and monotone depth of Boolean functions,Information Processing Letters,16, (1983), 41\u201342.","journal-title":"Information Processing Letters"},{"key":"BF02122698_CR23","doi-asserted-by":"crossref","unstructured":"A. C.Yao, Some Complexity Questions Related to Distributed Computing,Proc. 11th ACM STOC,1979, 209\u2013213.","DOI":"10.1145\/800135.804414"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02122698.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02122698\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02122698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,29]],"date-time":"2024-01-29T20:03:44Z","timestamp":1706558624000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02122698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,3]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1990,3]]}},"alternative-id":["BF02122698"],"URL":"https:\/\/doi.org\/10.1007\/bf02122698","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,3]]}}}