{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,1]],"date-time":"2025-02-01T05:26:27Z","timestamp":1738387587685,"version":"3.35.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-85363-3_23","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T19:29:28Z","timestamp":1219865368000},"page":"276-289","source":"Crossref","is-referenced-by-count":16,"title":["Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size"],"prefix":"10.1007","author":[{"given":"V.","family":"Arvind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Partha","family":"Mukhopadhyay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/11590156_6","volume-title":"FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science","author":"M. Agrawal","year":"2005","unstructured":"Agrawal, M.: Proving Lower Bounds Via Pseudo-random Generators. In: Ramanujam, R., Sen, S. (eds.) FSTTCS 2005. LNCS, vol.\u00a03821, pp. 92\u2013105. Springer, Heidelberg (2005)"},{"key":"23_CR2","unstructured":"Agrawal, M.: Rings and Integer Lattices in Computer Science. In: Barbados Workshop on Computational Complexity, Lecture no.\u00a09 (2007)"},{"issue":"4","key":"23_CR3","doi-asserted-by":"publisher","first-page":"1118","DOI":"10.1137\/S0097539798339041","volume":"29","author":"K. Reinhardt","year":"2000","unstructured":"Reinhardt, K., Allender, E.: Making Nondeterminism Unambiguous. SIAM J. Comput.\u00a029(4), 1118\u20131131 (2000)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"23_CR4","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1006\/jcss.1999.1646","volume":"59","author":"E. Allender","year":"1999","unstructured":"Allender, E., Reinhardt, K., Zhou, S.: Isolation, matching and counting uniform and nonuniform upper bounds. Journal of Computer and System Sciences\u00a059(2), 164\u2013181 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"#cr-split#-23_CR5.1","doi-asserted-by":"crossref","unstructured":"Arvind, V., Mukhopadhyay, P., Srinivasan, S.: New results on Noncommutative and Commutative Polynomial Identity Testing. In: Proceedings of the 23rd IEEE Conference on Computational Complexity (to appear, June 2008)","DOI":"10.1109\/CCC.2008.22"},{"key":"#cr-split#-23_CR5.2","unstructured":"Technical report version in ECCC report TR08-025 (2008)"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Wee, H.: More on Noncommutative Polynomial Identity Testing. In: Proc. of the 20th Annual Conference on Computational Complexity, pp. 92\u201399 (2005)","DOI":"10.1109\/CCC.2005.13"},{"issue":"1","key":"23_CR7","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539705447359","volume":"37","author":"S. Chien","year":"2007","unstructured":"Chien, S., Sinclair, A.: Algebras with Polynomial Identities and Computing the Determinants. SIAM J. of Comput.\u00a037(1), 252\u2013266 (2007)","journal-title":"SIAM J. of Comput."},{"key":"23_CR8","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979)"},{"issue":"4","key":"23_CR9","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1016\/S0022-0000(02)00024-7","volume":"65","author":"R. Impagliazzo","year":"2002","unstructured":"Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences\u00a065(4), 672\u2013694 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomization of polynomial identity tests means proving circuit lower bounds. In: Proc. of the thirty-fifth annual ACM Sym. on Theory of computing, pp. 355\u2013364 (2003)","DOI":"10.1145\/780542.780595"},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"Klivans, A.R., Spielman, D.A.: Randomness Efficient Identity Testing. In: Proceedings of the 33rd Symposium on Theory of Computing (STOC), pp. 216\u2013223 (2001)","DOI":"10.1145\/380752.380801"},{"key":"23_CR12","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/28395.383347","volume-title":"Proc. of the nineteenth annual ACM conference on Theory of Computing","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U., Vazirani, V.: Matching is as easy as matrix inversion. In: Proc. of the nineteenth annual ACM conference on Theory of Computing, pp. 345\u2013354. ACM Press, New York (1987)"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Lower bounds for non-commutative computation. In: Proc. of the 23rd annual ACM Sym. on Theory of computing, pp. 410\u2013418 (1991)","DOI":"10.1145\/103418.103462"},{"issue":"2","key":"23_CR14","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1137\/S0097539791195245","volume":"23","author":"H. Narayanan","year":"1994","unstructured":"Narayanan, H., Saran, H., Vazirani, V.V.: Randomized Parallel Algorithms for Matroid Union and Intersection, With Applications to Arboresences and Edge-Disjoint Spanning Trees. SIAM J. Comput.\u00a023(2), 387\u2013397 (1994)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"23_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-005-0188-8","volume":"14","author":"R. Raz","year":"2005","unstructured":"Raz, R., Shpilka, A.: Deterministic polynomial identity testing in non commutative models. Computational Complexity\u00a014(1), 1\u201319 (2005)","journal-title":"Computational Complexity"},{"issue":"4","key":"23_CR16","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast Probabilistic algorithm for verification of polynomial identities. J. ACM\u00a027(4), 701\u2013717 (1980)","journal-title":"J. ACM"},{"key":"23_CR17","volume-title":"Progress in Theoretical Computer Science","author":"H. Straubing","year":"1994","unstructured":"Straubing, H.: Finite automata, formal logic, and circuit complexity. In: Progress in Theoretical Computer Science, Birkhuser Boston Inc., Boston (1994)"},{"issue":"3","key":"23_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as Easy as Detecting Unique Solutions. Theor. Comput. Sci.\u00a047(3), 85\u201393 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Proc. of the Int. Sym. on Symbolic and Algebraic Computation, pp. 216\u2013226 (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T18:12:34Z","timestamp":1738347154000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540853626","9783540853633"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}