{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T17:39:56Z","timestamp":1761154796728},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2005,7,1]],"date-time":"2005-07-01T00:00:00Z","timestamp":1120176000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2005,7,1]],"date-time":"2005-07-01T00:00:00Z","timestamp":1120176000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2005,11]]},"DOI":"10.1007\/s00200-005-0180-1","type":"journal-article","created":{"date-parts":[[2005,7,1]],"date-time":"2005-07-01T12:00:53Z","timestamp":1120219253000},"page":"307-317","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Noisy interpolation of sparse polynomials in finite fields"],"prefix":"10.1007","volume":"16","author":[{"given":"Igor","family":"Shparlinski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arne","family":"Winterhof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,1]]},"reference":[{"key":"180_CR1","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1137\/S0097539796297577","volume":"28","author":"Ar","year":"1999","unstructured":"Ar, S., Lipton, R., Rubinfeld, R., Sudan, M.: Reconstructing algebraic functions from erroneous data. SIAM J. Comput. 28, 487\u2013510 (1999)","journal-title":"SIAM J. Comput."},{"key":"180_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Sudan, M.: Improved low-degree testing and its applications. In: Proc. 29nd ACM Symp. on Theory of Comp. 1997, New York: ACM 1999, pp. 485\u2013495","DOI":"10.1145\/258533.258642"},{"key":"180_CR3","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/3-540-45539-6_4","volume":"1807","author":"Bleichenbacher","year":"2000","unstructured":"Bleichenbacher, D., Nguyen, P.Q.: Noisy polynomial interpolation and noisy Chinese remaindering. Lect. Notes in Comp. Sci. 1807, 53\u201369 (2000)","journal-title":"Lect. Notes in Comp. Sci."},{"key":"180_CR4","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/3-540-68697-5_11","volume":"1109","author":"Boneh","year":"1996","unstructured":"Boneh, D., Venkatesan, R.: Hardness of computing the most significant bits of secret keys in Diffie\u2013Hellman and related schemes. Lect. Notes in Comp. Sci. 1109, 129\u2013142 (1996)","journal-title":"Lect. Notes in Comp. Sci."},{"key":"180_CR5","unstructured":"Boneh, D., Venkatesan, R.: Rounding in lattices and its cryptographic applications. In: Proc. 8th Annual ACM-SIAM Symp. on Discr. Algorithms, pp. 675\u2013681. New York: ACM 1997"},{"key":"180_CR6","unstructured":"Chistov, A.L., Karpinski, M.: Fast interpolation algorithms for sparse polynomials with respect to the size of coefficients. Research Report 85109\u2013CS, Bonn Univ., 1994"},{"key":"180_CR7","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0304-3975(91)90157-W","volume":"84","author":"Clausen","year":"1991","unstructured":"Clausen, M., Dress, A., Grabmeier, J., Karpinski, M.: On zero testing and interpolation of k-sparse multivariate polynomials over finite fields. Theor. Comp. Sci. 84, 151\u2013164 (1991)","journal-title":"Theor. Comp. Sci."},{"key":"180_CR8","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1112\/S0024610702004040","volume":"67","author":"Cochrane","year":"2003","unstructured":"Cochrane, T., Pinner, C., Rosenhouse, J.: Bounds on exponential sums and the polynomial Waring problem mod p. J. London Math. Soc. 67, 319\u2013336 (2003)","journal-title":"J. London Math. Soc."},{"key":"180_CR9","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/s00037-002-0174-3","volume":"11","author":"Codenotti","year":"2002","unstructured":"Codenotti, B., Shparlinski, I.E., Winterhof, A.: Non-approximability of the permanent of structured matrices over finite fields. Comp. Compl. 11, 158\u2013170 (2002)","journal-title":"Comp. Compl."},{"key":"180_CR10","unstructured":"von zur Gathen, J., Shparlinski, I.E.: Polynomial interpolation from multiples, In: Proc. 15th ACM-SIAM Symposium on Discrete Algorithms, SIAM 2004 pp. 1125\u20131130"},{"key":"180_CR11","first-page":"1","volume":"TR1998-060","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Rubinfeld, R., Sudan, M.: Learning polynomials with queries: the highly noisy case. Electronic Colloq. on Comp. Compl., Univ. of Trier TR1998-060, 1\u201334 (1998)","journal-title":"Electronic Colloq. on Comp. Compl., Univ. of Trier"},{"key":"180_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539791194069","volume":"23","author":"Grigoriev","year":"1994","unstructured":"Grigoriev, D., Karpinski, M., Singer, M.: Computational complexity of sparse rational interpolation. SIAM J. Comput. 23, 1\u201311 (1994)","journal-title":"SIAM J. Comput."},{"key":"180_CR13","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.782097","volume":"45","author":"Guruswami","year":"1999","unstructured":"Guruswami, V., Sudan, M.: Improved decoding of Reed\u2013Solomon and algebraic geometric codes. IEEE Trans. Inform. Theory 45, 1757\u20131767 (1999)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"180_CR14","first-page":"1","volume":"TR2001-014","author":"M. Kiwi","year":"2001","unstructured":"Kiwi, M., Magniez, F., Santha, M.: Exact and approximate testing\/correcting of algebraic functions: A survey'. Electronic Colloq. on Comp. Compl., Univ. of Trier TR2001-014, 1\u201349 (2001)","journal-title":"Electronic Colloq. on Comp. Compl., Univ. of Trier"},{"key":"180_CR15","doi-asserted-by":"crossref","unstructured":"Klivans, A.R., Spielman, D.A.: Randomness efficient identity testing of multivariate polynomials. In: Proc. 33rd ACM Symp. on Theory of Comp., ACM 2001 pp. 216\u2013223","DOI":"10.1145\/380752.380801"},{"key":"180_CR16","doi-asserted-by":"crossref","unstructured":"Lewin, D., Vadhan, S.: Checking polynomial identities over any field: Towards a derandomization? In: Proc. 30th ACM Symp. on Theory of Comp., ACM 1998, pp. 438\u2013447","DOI":"10.1145\/276698.276856"},{"key":"180_CR17","doi-asserted-by":"crossref","unstructured":"Lidl, R., Niederreiter, H.: Finite Fields. Cambridge: University Press 1997","DOI":"10.1017\/CBO9780511525926"},{"key":"180_CR18","unstructured":"Lipton, R., Vishnoi, N.: Deterministic identity testing for multivariate polynomials. In: Proc. 14th ACM-SIAM Symp. on Discr. Algorithms, SIAM 2003 pp. 756\u2013760"},{"key":"180_CR19","unstructured":"Micciancio, D.: On the hardness of the shortest vector problem, PhD Thesis, MIT 1998"},{"key":"180_CR20","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/10722028_4","volume":"1838","author":"Nguyen","year":"2000","unstructured":"Nguyen, P.Q., Stern, J.: Lattice reduction in cryptology: An update. Lect. Notes in Comp. Sci. 1838, 85\u2013112 (2000)","journal-title":"Lect. Notes in Comp. Sci."},{"key":"180_CR21","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1109\/18.748993","volume":"45","author":"Shokrollahi","year":"1999","unstructured":"Shokrollahi, M.A., Wasserman, H.: List decoding of algebraic-geometric codes. IEEE Trans. Inform. Theory 45, 432\u2013437 (1999)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"180_CR22","doi-asserted-by":"crossref","unstructured":"Shparlinski, I.E.: Sparse polynomial approximation in finite fields. In: Proc. 33rd ACM Symp. on Theory of Comput., pp. 209\u2013215. Crete: 2001","DOI":"10.1145\/380752.380803"},{"key":"180_CR23","unstructured":"Shparlinski, I.E., Winterhof, A.: A hidden number problem in small subgroups. Math. Comp., to appear"},{"key":"180_CR24","doi-asserted-by":"crossref","unstructured":"Shparlinski, I.E., Winterhof, A.: A nonuniform algorithm for the hidden number problem in subgroups. In: Proc. Intern. Workshop on Public Key Cryptography, Singapore, 2004, Lect. Notes in Comp. Sci. 2947, 416\u2013424 (2004)","DOI":"10.1007\/978-3-540-24632-9_30"},{"key":"180_CR25","unstructured":"Vinogradov, I.M.: Elements of Number Theory. New York: Dover Publications, Inc., 1954"},{"key":"180_CR26","unstructured":"Wasserman, H.: Reconstructing randomly sampled multivariate polynomials from highly noisy data. In: Proc. 9th ACM-SIAM Symp. on Discr. Algorithms, SIAM 1998 pp. 59\u201367"},{"key":"180_CR27","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF01438278","volume":"5","author":"Werther","year":"1994","unstructured":"Werther, K.: The complexity of sparse polynomial interpolation over finite fields. Appl. Algebra in Engin., Commun. and Comp. 5, 91\u2013103 (1994)","journal-title":"Appl. Algebra in Engin., Commun. and Comp."},{"key":"180_CR28","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Effective polynomial computation. Dordrecht: Kluwer Acad. Publ. 1993","DOI":"10.1007\/978-1-4615-3188-3"}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-005-0180-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00200-005-0180-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-005-0180-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-005-0180-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,14]],"date-time":"2022-05-14T00:16:52Z","timestamp":1652487412000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00200-005-0180-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7,1]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2005,11]]}},"alternative-id":["180"],"URL":"https:\/\/doi.org\/10.1007\/s00200-005-0180-1","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,7,1]]},"assertion":[{"value":"27 January 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2004","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}