{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:13:44Z","timestamp":1725455624875},"publisher-location":"Berlin\/Heidelberg","reference-count":16,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540537090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0020801","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T01:07:52Z","timestamp":1131844072000},"page":"228-237","source":"Crossref","is-referenced-by-count":5,"title":["Polynomial size constant depth circuits with a limited number of negations"],"prefix":"10.1007","author":[{"given":"Miklos","family":"Santha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher","family":"Wilson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai and M. Ben-Or (1984), A theorem on probabilistic constant depth circuits, Proceedings of 16th ACM STOC, 471\u2013474.","DOI":"10.1145\/800057.808715"},{"issue":"4","key":"19_CR2","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1145\/31846.31852","volume":"34","author":"M. Ajtai","year":"1987","unstructured":"M. Ajtai and Y. Gurevich (1987), Monotone versus positive, JACM 34:4, 1004\u20131015.","journal-title":"JACM"},{"issue":"1","key":"19_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s and E. Szemr\u00e9di (1983), An O(n log n) sorting network, Combinatorica 3:1, 1\u201319.","journal-title":"Combinatorica"},{"issue":"2","key":"19_CR4","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1109\/TC.1968.227401","volume":"17","author":"S. Akers","year":"1968","unstructured":"S. Akers (1968), On maximum inversion with minimum inverters, IEEE Transactions on Computers, 17:2, 134\u2013135.","journal-title":"IEEE Transactions on Computers"},{"issue":"1","key":"19_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"N. Alon and R. Boppana (1987), The monotone circuit complexity of Boolean functions, Combinatorica 7:1, 1\u201322.","journal-title":"Combinatorica"},{"issue":"2","key":"19_CR6","first-page":"222","volume":"32","author":"R. Boppana","year":"1986","unstructured":"R. Boppana (1986), Threshold functions and bounded depth monotone circuits, JCSS 32:2, 222\u2013229.","journal-title":"JCSS"},{"key":"19_CR7","first-page":"71","volume":"33","author":"M. Fischer","year":"1975","unstructured":"M. Fischer (1975), The complexity of negation-limited networks \u2014 a brief survey, Automata Theory and Formal Languages, 2nd GI Conference, ed. H. Brakhage, vol. 33 LNCS, Springer-Verlag, 71\u201382.","journal-title":"LNCS"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"A. Hajnal, W. Maass, P. Pudl\u00e1k, M. Szegedy, and G. Tur\u00e1n (1987), Threshold circuits of bounded depth, Proceedings of the 28th IEEE FOCS, 99\u2013110.","DOI":"10.1109\/SFCS.1987.59"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"J. Hastad (1986), Almost optimal lower bounds for small depth circuits, Proceedings of 18th ACM STOC, 6\u201320.","DOI":"10.1145\/12130.12132"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"N. Linial, Y. Mansour, and N. Nisan (1989), Constant depth circuits, Fourier transform and learnability, Proceedings of the 30th IEEE FOCS, 574\u2013579.","DOI":"10.1109\/SFCS.1989.63537"},{"issue":"3","key":"19_CR11","first-page":"694","volume":"4","author":"A. Markov","year":"1963","unstructured":"A. Markov (1963), On the inversion complexity of systems of Boolean functions, Soviet Math. Doklady 4:3, 694\u2013696.","journal-title":"Soviet Math. Doklady"},{"key":"19_CR12","first-page":"74","volume":"38","author":"E. A. Okolnishnikova","year":"1982","unstructured":"E. A. Okolnishnikova (1982), On the influence of negation on the complexity of a realization of monotone Boolean functions by formulas of bounded depth, Metody Diskretnogo Analiza 38, 74\u201380.","journal-title":"Metody Diskretnogo Analiza"},{"issue":"4","key":"19_CR13","first-page":"798","volume":"281","author":"A. A. Razborov","year":"1985","unstructured":"A. A. Razborov (1985), Lower bounds on the monotone complexity of some Boolean functions, Doklady Akademii Nauk SSSR 281:4, 798\u2013801.","journal-title":"Doklady Akademii Nauk SSSR"},{"issue":"4","key":"19_CR14","first-page":"393","volume":"7","author":"\u00c9. Tardos","year":"1987","unstructured":"\u00c9. Tardos (1987), The gap between monotone and non-monotone circuit complexity is exponential, Combinatorica 7:4, 393\u2013394.","journal-title":"Combinatorica"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"I. Wegener (1987), The complexity of Boolean functions, Wiley-Teubner series in computer science.","DOI":"10.1007\/3-540-18170-9_185"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"A. Yao (1989), Circuits and local computation, Proceedings of 20th ACM STOC, 186\u2013196.","DOI":"10.1145\/73007.73025"}],"container-title":["Lecture Notes in Computer Science","STACS 91"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0020801.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T16:45:03Z","timestamp":1607532303000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0020801"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540537090"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/bfb0020801","relation":{},"subject":[]}}