{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:17:15Z","timestamp":1725455835983},"publisher-location":"Berlin\/Heidelberg","reference-count":17,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354051659X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0026299","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T10:35:17Z","timestamp":1132396517000},"page":"138-147","source":"Crossref","is-referenced-by-count":3,"title":["Boolean circuit complexity of algebraic interpolation problems"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Adleman, L.M., Lenstra, H.K., Finding Irreducible Polynomials over Finite Fields, Proc. 18th ACM STOC (1986), pp. 350\u2013355.","DOI":"10.1145\/12130.12166"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Probabilistic Algorithms in Finite Fields, Proc. 22th IEEE FOCS (1981), pp. 394\u2013398.","DOI":"10.1109\/SFCS.1981.37"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Tiwari, P., A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation, Proc. 20th ACM STOC (1988), pp. 301\u2013309.","DOI":"10.1145\/62212.62241"},{"key":"8_CR4","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1090\/S0025-5718-1970-0276200-X","volume":"24","author":"E.R. Berlekamp","year":"1970","unstructured":"Berlekamp, E.R., Factoring Polynomials over Large Finite Fields, Math. Comp. 24 (1970), pp. 713\u2013753.","journal-title":"Math. Comp."},{"key":"8_CR5","unstructured":"Cauchy, A.L., Exercises d'Analyse et de Phys. Math., Vol 2, Paris, Bachelier (1841), pp.151\u2013159."},{"key":"8_CR6","unstructured":"Clausen, M., Dress, A., Grabmeier, J., Karpinski, M., On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials over Finite Fields, Research Report No.8522-CS, University of Bonn (1988); to appear in Theoretical Computer Science (1989)."},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"Cook, S.A., A Taxonomy of Problems with Fast Parallel Algorithms, Information and Control 64 (1985), pp. 2\u201322.","journal-title":"Information and Control"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"von zur Gathen, J., Factoring Sparse Multivariate Polynomials, Proc. 24th IEEE FOCS (1983), pp. 172\u2013179.","DOI":"10.1109\/SFCS.1983.15"},{"key":"8_CR9","first-page":"808","volume":"13","author":"J. Gathen von zur","year":"1984","unstructured":"von zur Gathen, J., Parallel Algorithm for Algebraic Problems, SIAM J. Comput., 13 (1984), 808\u2013824.","journal-title":"SIAM J. Comput."},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Grigoriev, D.Y., Karpinski, M., The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents is in NC, Proc. 28th IEEE FOCS (1987), Los Angeles, 1987, pp. 166\u2013172.","DOI":"10.1109\/SFCS.1987.56"},{"key":"8_CR11","unstructured":"Grigoriev, D.Y., Karpinski, M., Singer, M.F., Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields, Research Report No.8523-CS, University of Bonn (1988); submitted to SIAM J. Comput., 1988."},{"key":"8_CR12","unstructured":"Kaltofen, E., Computing with Polynomials Given by Straight-Line Programs I, Greatest Common Divisors, Proc. 17 th ACM STOC (1985), pp. 131\u2013142."},{"key":"8_CR13","unstructured":"Kaltofen, E., Trager, B., Computing with Polynomials Given by Black Boxes for their Evaluations: Greatest Common Divisor, Factorization, Seperation of Numerators and Denominators, Proc. 29 th IEEE FOCS (1988), pp. 296\u2013305."},{"key":"8_CR14","series-title":"Research Report","volume-title":"A Survey of Parallel Algorithms for Shared-Memory Machines","author":"R.M. Karp","year":"1988","unstructured":"Karp, R.M., Remachandran, V., A Survey of Parallel Algorithms for Shared-Memory Machines, Research Report No. UCB\/CSD 88\/407, University of California, Berkeley (1988); to appear in Handbook of Theoretical Computer Science, North Holland (1989)."},{"key":"8_CR15","unstructured":"Lidl, H., Niederreiter, H., Finite Fields, Encyclopedia of Mathematics and its Applications, Vol.10, Cambridge University Press (1983)."},{"key":"8_CR16","unstructured":"MacWilliams, F.J., Sloane, N.J.A., The Theory of Error Correcting Codes, North Holland (1972)."},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Wegener, I., The Complexity of Boolean Functions, Teubner (1987).","DOI":"10.1007\/3-540-18170-9_185"}],"container-title":["Lecture Notes in Computer Science","CSL '88"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0026299.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:56:00Z","timestamp":1607550960000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0026299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354051659X"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0026299","relation":{},"subject":[]}}