{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:57:06Z","timestamp":1725796626028},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319087825"},{"type":"electronic","value":"9783319087832"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08783-2_51","type":"book-chapter","created":{"date-parts":[[2014,7,5]],"date-time":"2014-07-05T14:04:30Z","timestamp":1404569070000},"page":"596-607","source":"Crossref","is-referenced-by-count":1,"title":["Depth Lower Bounds against Circuits with Sparse Orientation"],"prefix":"10.1007","author":[{"given":"Sajin","family":"Koroth","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayalal","family":"Sarma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"51_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-62034-6_33","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"E. Allender","year":"1996","unstructured":"Allender, E.: Circuit Complexity before the Dawn of the New Millennium. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 1\u201318. Springer, Heidelberg (1996)"},{"key":"51_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-540-79709-8_2","volume-title":"Computer Science \u2013 Theory and Applications","author":"E. Allender","year":"2008","unstructured":"Allender, E.: Cracks in the defenses: Scouting out approaches on circuit lower bounds. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) CSR 2008. LNCS, vol.\u00a05010, pp. 3\u201310. Springer, Heidelberg (2008)"},{"issue":"1","key":"51_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"Alon, N., Boppana, R.B.: The Monotone Circuit Complexity of Boolean Functions. Combinatorica\u00a07(1), 1\u201322 (1987)","journal-title":"Combinatorica"},{"issue":"1","key":"51_CR4","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1137\/S0097539701396959","volume":"35","author":"K. Amano","year":"2005","unstructured":"Amano, K., Maruoka, A.: A superpolynomial lower bound for a circuit computing the clique function with at most (1\/6) log log n negation gates. SIAM Journal on Computing\u00a035(1), 201\u2013216 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"51_CR5","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Canad. J. Math.\u00a017, 449\u2013467 (1965)","journal-title":"Canad. J. Math."},{"key":"51_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/3-540-07407-4_9","volume-title":"Automata Theory and Formal Languages","author":"M. Fischer","year":"1975","unstructured":"Fischer, M.: The Complexity of Negation-limited Networks \u2014 A Brief Survey. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol.\u00a033, pp. 71\u201382. Springer, Heidelberg (1975)"},{"issue":"3","key":"51_CR7","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1137\/S0097539792282965","volume":"26","author":"R. Impagliazzo","year":"1997","unstructured":"Impagliazzo, R., Paturi, R., Saks, M.E.: Size-depth tradeoffs for threshold circuits. SIAM Journal of Computing\u00a026(3), 693\u2013707 (1997)","journal-title":"SIAM Journal of Computing"},{"key":"51_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/3-540-45687-2_29","volume-title":"Mathematical Foundations of Computer Science 2002","author":"K. Iwama","year":"2002","unstructured":"Iwama, K., Morizumi, H.: An explicit lower bound of 5n-o(n) for boolean circuits. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 353\u2013364. Springer, Heidelberg (2002)"},{"issue":"2","key":"51_CR9","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.ipl.2003.10.003","volume":"89","author":"S. Jukna","year":"2004","unstructured":"Jukna, S.: On the minimum number of negations leading to super-polynomial savings. Information Processing Letters\u00a089(2), 71\u201374 (2004)","journal-title":"Information Processing Letters"},{"key":"51_CR10","doi-asserted-by":"crossref","unstructured":"Jukna, S.: Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics, vol.\u00a027. Springer New York Inc. (2012)","DOI":"10.1007\/978-3-642-24508-4"},{"key":"51_CR11","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: Monotone Circuits for Connectivity Require Super-logarithmic Depth. In: STOC, pp. 539\u2013550 (1988)","DOI":"10.1145\/62212.62265"},{"key":"51_CR12","unstructured":"Lov\u00e1sz, L.: On determinants, matchings, and random algorithms. In: Symposium on Fundamentals of Computation Theory (FCT), pp. 565\u2013574 (1979)"},{"key":"51_CR13","doi-asserted-by":"crossref","unstructured":"Raz, R., Wigderson, A.: Probabilistic communication complexity of boolean relations. In: Proc. of the 30th FOCS, pp. 562\u2013567 (1989)","DOI":"10.1109\/SFCS.1989.63535"},{"issue":"3","key":"51_CR14","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1145\/146637.146684","volume":"39","author":"R. Raz","year":"1992","unstructured":"Raz, R., Wigderson, A.: Monotone circuits for matching require linear depth. Journal of ACM\u00a039(3), 736\u2013744 (1992)","journal-title":"Journal of ACM"},{"key":"51_CR15","unstructured":"Razborov, A.A.: Lower Bounds for Monotone Complexity of Some Boolean Functions. Soviet Math. Doklady, 354\u2013357 (1985)"},{"issue":"6","key":"51_CR16","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF01157687","volume":"37","author":"A.A. Razborov","year":"1985","unstructured":"Razborov, A.A.: Lower bounds on monotone complexity of the logical permanent. Mathematical Notes\u00a037(6), 485\u2013493 (1985)","journal-title":"Mathematical Notes"},{"key":"51_CR17","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: The shrinkage exponent of de morgan formulas is 2. SIAM Journal on Computing (1998)","DOI":"10.1137\/S0097539794261556"},{"key":"51_CR18","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer New York Inc. (1999)","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08783-2_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T07:16:25Z","timestamp":1558941385000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08783-2_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319087825","9783319087832"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08783-2_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}