{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:18:02Z","timestamp":1725549482853},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240587"},{"type":"electronic","value":"9783540305385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30538-5_38","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:40:30Z","timestamp":1268401230000},"page":"460-468","source":"Crossref","is-referenced-by-count":2,"title":["Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching Require Exponential Size"],"prefix":"10.1007","author":[{"given":"Ashok Kumar","family":"Ponnuswami","sequence":"first","affiliation":[]},{"given":"H.","family":"Venkateswaran","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"38_CR1","doi-asserted-by":"publisher","first-page":"874","DOI":"10.1145\/322326.322341","volume":"29","author":"M. Jerrum","year":"1982","unstructured":"Jerrum, M., Snir, M.: Some exact complexity results for straight-line computations over semirings. J. ACM\u00a029, 874\u2013897 (1982)","journal-title":"J. ACM"},{"key":"38_CR2","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1145\/62212.62265","volume-title":"Proceedings of the twentieth annual ACM symposium on Theory of computing","author":"M. Karchmer","year":"1988","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. In: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 539\u2013550. ACM Press, New York (1988)"},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"Lewis II, P.M., Stearns, R.E., Hartmanis, J.: Memory bounds for recognition of context-free and context-sensitive languages. In: Conf. Record Switching Circ. Theory and Log. Des., pp. 191\u2013202 (1965)","DOI":"10.1109\/FOCS.1965.14"},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"Nisan, N., Wigderson, A.: Lower bounds on arithmetic circuits via partial derivatives. In: Proceedings of the 36th FOCS, pp. 16\u201325 (1996)","DOI":"10.1007\/BF01294256"},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"Raz, R.: Multi-linear formulas for permanent and determinant are of super-polynomial size. Electronic Colloquium on Computational Complexity\u00a067 (2003)","DOI":"10.1145\/1007352.1007353"},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"Raz, R., Wigderson, A.: Monotone circuits for matching require linear depth. In: ACM Symposium on Theory of Computing, pp. 287\u2013292 (1990)","DOI":"10.1145\/100216.100253"},{"key":"38_CR7","first-page":"798","volume":"281","author":"A.A. Razborov","year":"1985","unstructured":"Razborov, A.A.: Lower bounds on the monotone complexity of some boolean functions. Doklady Akademii Nauk SSSR\u00a0281, 798\u2013801 (1985) (in Russian); English translation in Soviet Mathematics Doklady 31, 354\u2013357 (1985)","journal-title":"Doklady Akademii Nauk SSSR"},{"issue":"2","key":"38_CR8","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W.L. Ruzzo","year":"1980","unstructured":"Ruzzo, W.L.: Tree-size bounded alternation. Journal of Computer and System Sciences\u00a021(2), 218\u2013235 (1980)","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR9","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02122563","volume":"8","author":"E. Tardos","year":"1988","unstructured":"Tardos, E.: The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica\u00a08, 141\u2013142 (1988)","journal-title":"Combinatorica"},{"key":"38_CR10","volume-title":"The complexity of Boolean functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: The complexity of Boolean functions. John Wiley & Sons, Inc., Chichester (1987)"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30538-5_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:58:55Z","timestamp":1605761935000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30538-5_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240587","9783540305385"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30538-5_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}