{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:01:43Z","timestamp":1725562903209},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_28","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"306-317","source":"Crossref","is-referenced-by-count":2,"title":["Counting Classes and the Fine Structure between NC 1 and L"],"prefix":"10.1007","author":[{"given":"Samir","family":"Datta","sequence":"first","affiliation":[]},{"given":"Meena","family":"Mahajan","sequence":"additional","affiliation":[]},{"given":"B. V. Raghavendra","family":"Rao","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Thomas","sequence":"additional","affiliation":[]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"28_CR1","first-page":"33","volume":"28","author":"E. Allender","year":"2004","unstructured":"Allender, E.: Arithmetic circuits and counting complexity classes. In: Krajicek, J. (ed.) Complexity of Computations and Proofs. Quaderni di Matematica, vol.\u00a013, pp. 33\u201372. Seconda Universita di Napoli (2004); An earlier version appeared in the Complexity Theory Column. SIGACT News\u00a028(4), 2\u201315 (December 1997)","journal-title":"SIGACT News"},{"issue":"2","key":"28_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s000370050023","volume":"8","author":"E. Allender","year":"1999","unstructured":"Allender, E., Beals, R., Ogihara, M.: The complexity of matrix rank and feasible systems of linear equations. Computational Complexity\u00a08(2), 99\u2013126 (1999)","journal-title":"Computational Complexity"},{"key":"28_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1051\/ita\/1996300100011","volume":"30","author":"E. Allender","year":"1996","unstructured":"Allender, E., Ogihara, M.: Relationships among PL, #L, and the determinant. RAIRO Theoretical Information and Applications\u00a030, 1\u201321 (1996); Conference version in Proc. 9th IEEE Structure in Complexity Theory Conference, pp. 267\u2013278 (1994)","journal-title":"RAIRO Theoretical Information and Applications"},{"key":"28_CR4","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A. Barrington","year":"1989","unstructured":"Barrington, D.A.: Bounded-width polynomial size branching programs recognize exactly those languages in NC1. Journal of Computer and System Sciences\u00a038, 150\u2013164 (1989)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"28_CR5","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1006\/jcss.1995.1017","volume":"50","author":"R. Beigel","year":"1995","unstructured":"Beigel, R., Reingold, N., Spielman, D.A.: PP is closed under intersection. Journal of Computer and System Sciences\u00a050(2), 191\u2013202 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR6","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1006\/jcss.1998.1588","volume":"57","author":"H. Caussinus","year":"1998","unstructured":"Caussinus, H., McKenzie, P., Th\u00e9rien, D., Vollmer, H.: Nondeterministic NC\n                1 computation. Journal of Computer and System Sciences\u00a057, 200\u2013212 (1998); Preliminary version in Proceedings of the 11th IEEE Conference on Computational Complexity, pp. 12\u201321 (1996)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"28_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0001","volume":"124","author":"L. Fortnow","year":"1996","unstructured":"Fortnow, L., Reingold, N.: PP is closed under truth-table reductions. Inf. Comput.\u00a0124(1), 1\u20136 (1996)","journal-title":"Inf. Comput."},{"issue":"4","key":"28_CR8","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1051\/ita\/1987210404191","volume":"21","author":"J. K\u00f6bler","year":"1987","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Wagner, K.W.: The difference and truth-table hierarchies for NP. Theoretical Informatics and Applications\u00a021(4), 419\u2013435 (1987)","journal-title":"Theoretical Informatics and Applications"},{"issue":"1","key":"28_CR9","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0304-3975(93)90255-R","volume":"107","author":"K.-J. Lange","year":"1993","unstructured":"Lange, K.-J.: Unambiguity of circuits. Theor. Comput. Sci.\u00a0107(1), 77\u201394 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"28_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1007\/978-3-642-03409-1_23","volume-title":"FCT","author":"M. Mahajan","year":"2009","unstructured":"Mahajan, M., Raghavendra Rao, B.V.: Small-space analogues of Valiant\u2019s classes. In: Ge\u0327bala, M. (ed.) FCT 2009. LNCS, vol.\u00a05699, pp. 250\u2013261. Springer, Heidelberg (2009)"},{"issue":"5","key":"28_CR11","doi-asserted-by":"publisher","first-page":"1430","DOI":"10.1137\/S0097539795295924","volume":"27","author":"M. Ogihara","year":"1998","unstructured":"Ogihara, M.: The PL hierarchy collapses. SIAM J. Comput.\u00a027(5), 1430\u20131437 (1998)","journal-title":"SIAM J. Comput."},{"key":"28_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer, New York (1999)"},{"issue":"1","key":"28_CR13","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/0890-5401(91)90078-G","volume":"91","author":"J. Gathen von zur","year":"1991","unstructured":"von zur Gathen, J., Seroussi, G.: Boolean circuits versus arithmetic circuits. Information and Computation\u00a091(1), 142\u2013154 (1991)","journal-title":"Information and Computation"},{"issue":"2","key":"28_CR14","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C.B. Wilson","year":"1985","unstructured":"Wilson, C.B.: Relativized circuit complexity. J. Comput. Syst. Sci.\u00a031(2), 169\u2013181 (1985)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:01:38Z","timestamp":1606186898000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}