{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:01:55Z","timestamp":1725562915838},"publisher-location":"Berlin, Heidelberg","reference-count":16,"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_55","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T16:17:45Z","timestamp":1281716265000},"page":"629-640","source":"Crossref","is-referenced-by-count":1,"title":["Enumeration of the Monomials of a Polynomial and Related Complexity Classes"],"prefix":"10.1007","author":[{"given":"Yann","family":"Strozecki","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"55_CR1","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1145\/62212.62241","volume-title":"Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing","author":"M. Ben-Or","year":"1988","unstructured":"Ben-Or, M.: A deterministic algorithm for sparse multivariate polynomial interpolation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 301\u2013309. ACM, New York (1988)"},{"issue":"3","key":"55_CR2","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/S0747-7171(08)80018-1","volume":"9","author":"R. Zippel","year":"1990","unstructured":"Zippel, R.: Interpolating polynomials from their values. Journal of Symbolic Computation\u00a09(3), 375\u2013403 (1990)","journal-title":"Journal of Symbolic Computation"},{"issue":"3-4","key":"55_CR3","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0747-7171(03)00088-9","volume":"36","author":"E. Kaltofen","year":"2003","unstructured":"Kaltofen, E., Lee, W.: Early termination in sparse interpolation algorithms. Journal of Symbolic Computation\u00a036(3-4), 365\u2013400 (2003)","journal-title":"Journal of Symbolic Computation"},{"key":"55_CR4","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1145\/380752.380801","volume-title":"Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing","author":"A. Klivans","year":"2001","unstructured":"Klivans, A., Spielman, D.: Randomness efficient identity testing of multivariate polynomials. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 216\u2013223. ACM, New York (2001)"},{"unstructured":"Arvind, V., Mukhopadhyay, P., Albers, S., Marion, J.: Quantum query complexity of multilinear identity testing. In: Symposium on Theoretical Aspects of Computer Science, vol.\u00a03, pp. 87\u201398 (2009)","key":"55_CR5"},{"doi-asserted-by":"crossref","unstructured":"Karnin, Z., Shpilka, A.: Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. In: Conference on Computational Complexity, pp. 280\u2013291 (2008)","key":"55_CR6","DOI":"10.1109\/CCC.2008.15"},{"issue":"3","key":"55_CR7","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: On generating all maximal independent sets. Inf. Process. Lett.\u00a027(3), 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"3-4","key":"55_CR8","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0020-0190(00)00023-5","volume":"74","author":"D.J. Kavvadias","year":"2000","unstructured":"Kavvadias, D.J., Sideri, M., Stavropoulos, E.C.: Generating all maximal models of a boolean expression. Inf. Process. Lett.\u00a074(3-4), 157\u2013162 (2000)","journal-title":"Inf. Process. Lett."},{"unstructured":"Bagan, G.: Algorithmes et Complexit\u00e9 des Probl\u00e8mes d\u2019\u00c9num\u00e9ration pour l\u2019\u00c9valuation de Requ\u00eates Logiques. PhD thesis, Universit\u00e9 de Caen (2009)","key":"55_CR9"},{"key":"55_CR10","volume-title":"A course in enumeration","author":"M. Aigner","year":"2007","unstructured":"Aigner, M.: A course in enumeration. Springer, Heidelberg (2007)"},{"issue":"4","key":"55_CR11","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1145\/322217.322225","volume":"27","author":"J. Schwartz","year":"1980","unstructured":"Schwartz, J.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM\u00a027(4), 717 (1980)","journal-title":"Journal of the ACM"},{"unstructured":"Duris, D.: Acyclicit\u00e9 des hypergraphes et liens avec la logique sur les structures relationnelles finies. PhD thesis, Universit\u00e9 Paris Diderot - Paris 7 (2009)","key":"55_CR12"},{"issue":"2","key":"55_CR13","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0095-8956(80)90066-0","volume":"28","author":"L. Lov\u00e1sz","year":"1980","unstructured":"Lov\u00e1sz, L.: Matroid matching and some applications. J. Combin. Theory Ser. B\u00a028(2), 208\u2013236 (1980)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"27","key":"55_CR14","doi-asserted-by":"publisher","first-page":"1397","DOI":"10.1155\/S1073792802111044","volume":"2002","author":"G. Masbaum","year":"2002","unstructured":"Masbaum, G., Vaintrob, A.: A new matrix-tree theorem. International Mathematics Research Notices\u00a02002(27), 1397 (2002)","journal-title":"International Mathematics Research Notices"},{"key":"55_CR15","first-page":"0812","volume":"arXiv","author":"S. Caracciolo","year":"2008","unstructured":"Caracciolo, S., Masbaum, G., Sokal, A., Sportiello, A.: A randomized polynomial-time algorithm for the Spanning Hypertree Problem on 3-uniform hypergraphs. Arxiv preprint arXiv:0812.3593 (2008)","journal-title":"Arxiv preprint"},{"issue":"4","key":"55_CR16","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0020-0190(79)90023-1","volume":"8","author":"J. Plesn\u00edk","year":"1979","unstructured":"Plesn\u00edk, J.: The np-completeness of the hamiltonian cycle problem in planar digraphs with degree bound two. Inf. Process. Lett.\u00a08(4), 199\u2013201 (1979)","journal-title":"Inf. Process. Lett."}],"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_55.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:01:49Z","timestamp":1606168909000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}