{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:48:01Z","timestamp":1742914081622,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":19,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781461472575"},{"type":"electronic","value":"9781461472582"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-1-4614-7258-2_26","type":"book-chapter","created":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T18:28:13Z","timestamp":1375381693000},"page":"425-433","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Small Size Approximation Models"],"prefix":"10.1007","author":[{"given":"Alexander A.","family":"Razborov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,5,20]]},"reference":[{"issue":"1","key":"26_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N Alon","year":"1987","unstructured":"N. Alon and R. Boppana. The monotone circuit complexity of Boolean functions. Combinatorica, 7(1):1\u201322, 1987.","journal-title":"Combinatorica"},{"key":"26_CR2","volume-title":"A note on a theorem of Razborov","author":"D A Barrington","year":"1986","unstructured":"D. A. Barrington. A note on a theorem of Razborov. Technical report, University of Massachusetts, 1986."},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"R. B. Boppana and M. Sipser. The complexity of finite functions. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, vol. A (Algorithms and Complexity), chapter\u00a014, pages\u00a0757\u2013804. Elsevier Science Publishers B.V. and The MIT Press, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"26_CR4","unstructured":"M. Karchmer. On proving lower bounds for circuit size. In Proceedings of the 8th Structure in Complexity Theory Annual Conference, pages\u00a0112\u2013118, 1993."},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"M. Karchmer and A. Wigderson. Characterizing non-deterministic circuit size. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, pages\u00a0532\u2013540, 1993.","DOI":"10.1145\/167088.167230"},{"key":"26_CR6","unstructured":"M. Karchmer and A. Wigderson. On span programs. In Proceedings of the 8th Structure in Complexity Theory Annual Conference, pages\u00a0102\u2013111, 1993."},{"key":"26_CR7","volume-title":"Modified Branching Programs and Their Computational Power, Lecture Notes in Computer Science, 370","author":"C Meinel","year":"1989","unstructured":"C. Meinel. Modified Branching Programs and Their Computational Power, Lecture Notes in Computer Science, 370. Springer-Verlag, New York\/Berlin, 1989."},{"key":"26_CR8","unstructured":"K. Nakayama and A. Maruoka. Loop circuits and their relation to Razborov\u2019s approximation model. Manuscript, 1992."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"A. Razborov. On the method of approximation. In Proceedinqs of the 21st ACM Symposium on Theory of Computing, pages\u00a0167\u2013176, 1989.","DOI":"10.1145\/73007.73023"},{"key":"26_CR10","unstructured":"A. Razborov. Bounded Arithmetic and lower bounds in Boolean complexity. To appear in the volume Feasible Mathematics II, 1993."},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th ACM Symposium on Theory of Computing, pages\u00a077\u201382, 1987.","DOI":"10.1145\/28395.28404"},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02122563","volume":"8","author":"\u00c9. Tardos","year":"1988","unstructured":"\u00c9. Tardos. The gap between monotone and nonmonotone circuit complexity is exponential. Combinatorica, 8:141\u2013142, 1988.","journal-title":"Combinatorica"},{"key":"26_CR13","unstructured":"A. Wigderson. The fusion method for lower bounds in circuit complexity. In Combinatorics, Paul Erdos is Eighty. 1993."},{"key":"26_CR14","unstructured":"A. E. Andreev. Ob odnom metode poluqeni \u00a0ninih ocenok slonosti individualnyh monotonnyh funkci. DAN CCCP, 282(5):1033\u20131037, 1985. A.E. Andreev, On a method for obtaining lower bounds for the complexity of individual monotone functions. Soviet Math. Dokl. 31(3):530\u2013534, 1985."},{"issue":"1","key":"26_CR15","first-page":"3","volume":"26","author":"A. E. Andreev","year":"1987","unstructured":"A. E. Andreev. Ob odnom metode poluqeni \u00a0ffektivnyh ninih ocenok monotonno\u00a0slonosti. Algebra \u00ec logika, 26(1):3\u201321, 1987: A.E. Andreev, On one method of obtaining effective lower bounds of monotone complexity. Algebra i logika, 26(1):3\u201321, 1987. In Russian.","journal-title":"Algebra \u00ec logika"},{"issue":"4","key":"26_CR16","first-page":"798","volume":"281","author":"A. A. Razborov","year":"1985","unstructured":"A. A. Razborov. Ninie ocenki monotonno\u00a0slo nosti nekotoryh bulevyh funkci. DAN CCCP, 281(4):798\u2013801, 1985. A. A. Razborov, Lower bounds for the monotone complexity of some Boolean functions, Soviet Math. Dokl., 31:354\u2013357, 1985.","journal-title":"DAN CCCP"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"A. A. Razborov. Ninie ocenki monotonno\u00a0slonosti logiqeskogo permanenta. Mamem 3am., 37(6):887\u2013900, 1985. A. A. Razborov, Lower bounds of monotone complexity of the logical permanent function, Mathem. Notes of the Academy of Sci. of the USSR, 37:485\u2013493, 1985.","DOI":"10.1007\/BF01157687"},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"A. A. Razborov. Ninie ocenki razmera shem ograniqenno\u00a0glubiny v polnom bazise, soderawem funkci \u00a0logiqeskogo sloeni. Mamem 3am., 41(4):598- 607, 1987. A. A. Razborov, Lower bounds on the size of bounded-depth networks over a complete basis with logical addition, Mathem. Notes of the Academy of Sci. of the USSR, 41(4):333\u2013338, 1987.","DOI":"10.1007\/BF01137685"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"A. A. Razborov. Ninie ocenki slonosti realizacii simmetriqeskih bulevyh funkci\u00a0kontaktno-ventilnymi shemami. Matem, 3am., 48(6):79\u201391, 1990. A. A. Razborov, Lower bounds on the size of switching-and-rectifier networks for symmetric Boolean functions, Mathem. Notes of the Academy of Sci. of the USSR.","DOI":"10.1007\/BF01240265"}],"container-title":["The Mathematics of Paul Erd\u0151s I"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4614-7258-2_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T11:06:27Z","timestamp":1706180787000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-1-4614-7258-2_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9781461472575","9781461472582"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-1-4614-7258-2_26","relation":{},"subject":[],"published":{"date-parts":[[2013]]},"assertion":[{"value":"20 May 2013","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}