{"entities":{"Q1320441":{"pageid":1331191,"ns":120,"title":"Item:Q1320441","lastrevid":67165935,"modified":"2026-04-12T15:44:08Z","type":"item","id":"Q1320441","labels":{"en":{"language":"en","value":"The complexity of sparse polynomial interpolation over finite fields"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 556284"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$CF996109-ACBB-4FBE-B87D-C4E93D273F2F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3a7e3d6787abd42c02774a4a32413a6c50998220","datavalue":{"value":{"text":"The complexity of sparse polynomial interpolation over finite fields","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1320441$DE487041-4DEC-4C1E-A6B0-6462E7B61145","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"54b4da717537e4332f129fb514b976ea87f4f9a8","datavalue":{"value":"0813.11073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1320441$764C8A65-77E9-4CE5-B9CF-5CC26FF9B93F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cb5186811ac92ecff67d87517d8a2b82b97713db","datavalue":{"value":"10.1007/BF01438278","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1320441$B65C2FA7-C29B-4CC4-8DC4-539247D2424D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4219eba8c827e6e451d606cee37fd28b9ba3d90b","datavalue":{"value":{"entity-type":"item","numeric-id":1320440,"id":"Q1320440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$26A1A334-A970-499F-8185-9EFBC8DC02E4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e71b1a810c94176f33b214acd409208085d409e4","datavalue":{"value":{"entity-type":"item","numeric-id":162945,"id":"Q162945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$F505D75D-7B92-4BBC-87A5-823C7A62DA2D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"093fa04023e5f4c0c7c6ff4ef30755200a49a96c","datavalue":{"value":{"time":"+1995-06-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1320441$B542C5BB-4958-4CB8-B58C-5C858F21F781","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4516c8ecd2b930139073866dd8207c4553ab372a","datavalue":{"value":"The interpolation of \\(n\\)-variate polynomials \\(f\\) of degree \\(d = \\max \\deg_{X_ i}f\\) requires at least \\((d+1)^ n\\) evaluations of the unknown polynomial \\(f\\). Denote the number of nonzero coefficients of \\(f\\) its sparsity and call a polynomial \\(k\\)-sparse if its sparsity is at most \\(k\\). A set \\(A \\subseteq \\mathbb{R}^ n\\) is a test set if for all \\(n\\)-variate \\(k\\)-sparse polynomials \\(f \\neq 0\\) of degree at most \\(d\\) there is an \\(a \\in A\\) with \\(f(a) \\neq 0\\). An estimate of the size of a test set constructed by \\textit{M. Clausen}, \\textit{A. Dress}, \\textit{J. Grabmeier} and \\textit{M. Karpinski} [Theor. Comput. Sci. 84, 151-164 (1991; Zbl 0737.65002)] is given and the previously known lower bounds on the size of a minimal test set are improved. A new interpolation algorithm for arbitrary fields that uses only evaluations over the ground field is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1320441$6224CA66-0BFA-4345-99D6-44B1FE250609","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1320441$77A40163-3D7D-410D-8D7C-572ECBB875C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5005488ac12471348bfecb95099a57fd4da722ac","datavalue":{"value":"11T06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1320441$C467F25A-74C8-4A36-B398-1C84E0764101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1320441$D505506A-4245-4F81-84E6-A4DB5B06AD74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c51b93a482672aa9a8401eb9fb47da167f094352","datavalue":{"value":"65D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1320441$4C5E82C7-0B63-41B3-B01D-E67AA8455DF1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"06b629912aa0290460b9ccf78306db37f55c1bee","datavalue":{"value":"556284","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1320441$6E16A123-B7FA-4AA5-8B96-2E060A77D131","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d369ceee37d5961acaa52451162583f41c60fdd9","datavalue":{"value":"polynomial interpolation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1320441$65657CF7-7BC3-42D3-B17C-3C71598B5057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac07c7d6c5cdc2dbc4590f3ecbac0ebb59196bea","datavalue":{"value":"finite fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q1320441$B181CC4E-98EE-473A-A396-E42FC6370365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1320441$05A93A9E-F1BA-47A6-8E87-2E9D9966EEB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8581a4fe4c0d3571122fc96549003538cce73aa","datavalue":{"value":"sparse polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q1320441$B6C60136-FEBF-48FA-972D-BECDEB060C1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"292970f019b2a323be71a102b27329ae66de7ce3","datavalue":{"value":"interpolation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1320441$B232F705-4FCA-4EEF-B915-E6BD60714634","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d55353e7bc3d0614b86e9af78e82c119a2d0a9e0","datavalue":{"value":{"entity-type":"item","numeric-id":677137,"id":"Q677137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$794FAC01-F77C-417A-B52D-AAF84D5C6DEB","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$65794E1D-B3D3-4560-9BA5-279B993CA409","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f413798c4fad54cf113056f6f4118c35f7af2ade","datavalue":{"value":{"entity-type":"item","numeric-id":1178687,"id":"Q1178687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$20A56576-7F4A-4DDE-9263-C64805BA6745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"217d8cf310dde3cd1808ec9e7efded7efd352436","datavalue":{"value":{"entity-type":"item","numeric-id":3137705,"id":"Q3137705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$11A5284B-A0E4-41D4-8B31-0E496F94B726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b1a601d2d325d59af7d202f1f94462edd810b86","datavalue":{"value":{"entity-type":"item","numeric-id":3495652,"id":"Q3495652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$EA60331A-B834-4D9F-AA50-B03A7A2CB025","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f04ed41030a28fdf73b8f202bf30b859d792195","datavalue":{"value":{"entity-type":"item","numeric-id":5748889,"id":"Q5748889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$B7DFDA24-612A-415A-8251-C1E8FC4E0FCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52fb796594aa32d99f4e818726f7bf89a9fc8d31","datavalue":{"value":{"entity-type":"item","numeric-id":3765876,"id":"Q3765876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$61F3D899-092E-4172-9F4D-13DF854FC17C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5c1d50e9a7d7b878d14e5a3286f3528c2d7700b","datavalue":{"value":{"entity-type":"item","numeric-id":3359132,"id":"Q3359132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$EA1BDDED-101D-40AB-AB8C-B05864622993","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d73e5fdcd2644fcf8851cd00097d32d1e30f5f00","datavalue":{"value":{"entity-type":"item","numeric-id":3851616,"id":"Q3851616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$C14185A5-F2F7-4FAA-B92C-53A13E9E95A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a25a1fa95e7799812e4dba2e2a4326ed74549c9","datavalue":{"value":{"entity-type":"item","numeric-id":915342,"id":"Q915342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1320441$51709D8A-7D38-444C-88F5-A7632481D278","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d437006419f47ac02042eac20a7c23d4768945b4","datavalue":{"value":{"entity-type":"item","numeric-id":1701485,"id":"Q1701485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4237d3d880c9a6acaf30d5ee1254f705317df23b","datavalue":{"value":{"amount":"+0.8325147032737732","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1320441$BA0BE27B-1A34-4C09-93D5-008A4A95B86C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d410628589ea1aadfeb5075d6d05b87dd689c4d","datavalue":{"value":{"entity-type":"item","numeric-id":3495652,"id":"Q3495652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7cfdd31ce5c8aa8733033b3fd37e00561b64bc8","datavalue":{"value":{"amount":"+0.8303647041320801","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1320441$006170B0-A771-4D84-A8DA-2D4A1D84495E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5d05a0448f07d1e4ac4958a5888ed3d91e7abf7","datavalue":{"value":{"entity-type":"item","numeric-id":1178687,"id":"Q1178687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"573804fe6e063bdc2d688673277f739f42498102","datavalue":{"value":{"amount":"+0.829032301902771","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1320441$F10E7304-9F56-4F2D-A828-06C61AEB3F40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6112f9c6ced9dbb061d6921c1683466879ac9257","datavalue":{"value":{"entity-type":"item","numeric-id":2143469,"id":"Q2143469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14a40d5bef571f9ed83e2803af9fb688074136ec","datavalue":{"value":{"amount":"+0.8282475471496582","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1320441$0D7D0827-2105-4A26-9BDD-8C1072F1B65C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of sparse polynomial interpolation over finite fields","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_sparse_polynomial_interpolation_over_finite_fields"}}}}}