{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T06:10:27Z","timestamp":1737094227348,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540430025"},{"type":"electronic","value":"9783540452942"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45294-x_7","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T02:45:12Z","timestamp":1181616312000},"page":"70-82","source":"Crossref","is-referenced-by-count":5,"title":["The First-Order Isomorphism Theorem"],"prefix":"10.1007","author":[{"given":"Manindra","family":"Agrawal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,11,26]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"M. Agrawal, E. Allender, R. Impagliazzio, T. Pitassi, and S. Rudich. Reducing the complexity of reductions. In Proceedings of Annual ACM Symposium on the Theory of Computing, pages 730\u2013738, 1997.","DOI":"10.1145\/258533.258671"},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1006\/jcss.1998.1583","volume":"57","author":"M. Agrawal","year":"1998","unstructured":"M. Agrawal, E. Allender, and S. Rudich. Reductions in circuit complexity: An isomorphism theorem and a gap theorem. J. Comput. Sys. Sci., 57:127\u2013143, 1998.","journal-title":"J. Comput. Sys. Sci."},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"E. Allender, J. Balc\u00e1zar, and N. Immerman. A first-order isomorphism theorem. In Proceedings of the Symposium on Theoretical Aspects of Computer Science, 1993.","DOI":"10.1007\/3-540-56503-5_19"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0020-0190(91)90015-A","volume":"40","author":"E. Allender","year":"1991","unstructured":"E. Allender and V. Gore. Rudimentary reductions revisited. Information Processing Letters, 40:89\u201395, 1991.","journal-title":"Information Processing Letters"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"N. Alon, O. Goldreich, J. Hastad, and R. Peralta. Simple constructions of almost k-wise independent random variables. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science, pages 544\u2013553, 1990.","DOI":"10.1109\/FSCS.1990.89575"},{"issue":"2","key":"7_CR6","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jcss.1996.0068","volume":"53","author":"M. Agrawal","year":"1996","unstructured":"M. Agrawal. On the isomorphism problem for weak reducibilities. J. Comput. Sys. Sci., 53(2):267\u2013282, 1996.","journal-title":"J. Comput. Sys. Sci."},{"key":"7_CR7","unstructured":"M. Agrawal. Towards uniform AC0 isomorphisms. In Proceedings of the Conference on Computational Complexity, 2001. to be presented."},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"1","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis. On isomorphism and density of NP and other complete sets. SIAM Journal on Computing, 1:305\u2013322, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"74","author":"D. Barrington","year":"1990","unstructured":"D. Barrington, N. Immerman, and H. Straubing. On uniformity within NC1. J. Comput. Sys. Sci., 74:274\u2013306, 1990.","journal-title":"J. Comput. Sys. Sci."},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. Chandra","year":"1984","unstructured":"A. Chandra, L. Stockmeyer, and U. Vishkin. Constant depth reducibility. SIAM Journal on Computing, 13:423\u2013439, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"35","author":"P. Erd\u00f6s","year":"1960","unstructured":"P. Erd\u00f6s and R. Rado. Intersection theorems for systems of sets. J. London Math. Soc., 35:85\u201390, 1960.","journal-title":"J. London Math. Soc."},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz. The isomorphism conjecture holds relative to an oracle. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science, pages 30\u201339, 1992. To appear in SIAM J. Comput.","DOI":"10.1109\/SFCS.1992.267821"},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe, and M. Sipser. Parity, circuits, and the polynomial hierarchy. Mathematical Systems Theory, 17:13\u201327, 1984.","journal-title":"Mathematical Systems Theory"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1006\/inco.1995.1007","volume":"116","author":"N. Immerman","year":"1995","unstructured":"N. Immerman and S. Landau. The complexity of iterated multiplication. Information and Computation, 116:103\u2013116, 1995.","journal-title":"Information and Computation"},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages that capture complexity classes. SIAM Journal on Computing, 16:760\u2013778, 1987.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. Jones","year":"1975","unstructured":"N. Jones. Space-bounded reducibility among combinatorial problems. J. Comput. Sys. Sci., 11:68\u201385, 1975.","journal-title":"J. Comput. Sys. Sci."},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"S. Kurtz, S. Mahaney, and J. Royer. The structure of complete degrees. In A. Selman, editor, Complexity Theory Retrospective, pages 108\u2013146. Springer-Verlag, 1988.","DOI":"10.1007\/978-1-4612-4478-3_7"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"S. Kurtz, S. Mahaney, and J. Royer. The isomorphism conjecture fails relative to a random oracle. In Proceedings of Annual ACM Symposium on the Theory of Computing, pages 157\u2013166, 1989.","DOI":"10.1145\/73007.73022"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"S. Lindell. A purely logical characterization of circuit complexity. In Proceedings of the Structure in Complexity Theory Conference, pages 185\u2013192, 1992.","DOI":"10.1109\/SCT.1992.215393"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"J. Naor and M. Naor. Small-bias probability spaces: Efficient constructions and applications. In Proceedings of Annual ACM Symposium on the Theory of Computing, pages 213\u2013223, 1990.","DOI":"10.1145\/100216.100244"},{"issue":"2","key":"7_CR22","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"N. Nisan and A. Wigderson. Hardness vs. randomness. J. Comput. Sys. Sci., 49(2):149\u2013167, 1994.","journal-title":"J. Comput. Sys. Sci."},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"M. Sipser. Borel sets and circuit complexity. In Proceedings of Annual ACM Symposium on the Theory of Computing, pages 61\u201369, 1983.","DOI":"10.1145\/800061.808733"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45294-X_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:54:07Z","timestamp":1737093247000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45294-X_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540430025","9783540452942"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-45294-x_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}