{"entities":{"Q540394":{"pageid":542161,"ns":120,"title":"Item:Q540394","lastrevid":62607990,"modified":"2026-04-11T07:14:33Z","type":"item","id":"Q540394","labels":{"en":{"language":"en","value":"Efficient list decoding of a class of algebraic-geometry codes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5903544"}},"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":"Q540394$15C239AA-0400-42AF-A6DC-D440054B9EB7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dc31b3353ebcef82019db4ac97dbf0841cb69816","datavalue":{"value":{"text":"Efficient list decoding of a class of algebraic-geometry codes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q540394$5FE2BE0C-52EA-4C9B-AD26-B642C64B3DE1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"845a7f7af58cf489bb8d5cbab8b0c9dcf7f7f84c","datavalue":{"value":"1222.94045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540394$54D766E9-4500-427A-BE6A-40C06536A428","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"708731e2c40945e5651865e3f3c3a629b69ee009","datavalue":{"value":{"entity-type":"item","numeric-id":540393,"id":"Q540393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540394$833174BE-FAC0-461D-8005-E0F38C717C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"922f64ba998eecf3ac41dff32c2fe097cf3109ca","datavalue":{"value":{"entity-type":"item","numeric-id":162961,"id":"Q162961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540394$B71FFDA1-B4C0-4C96-B6FA-D0C274610079","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6930ab8e1ff702d6af91a0a660c081a26e7eb4f9","datavalue":{"value":{"entity-type":"item","numeric-id":259257,"id":"Q259257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540394$41870CC1-571D-4FF4-86BF-AE3991385269","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"97ec2afdf79c6632e29986375b104998c12b878d","datavalue":{"value":{"time":"+2011-06-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q540394$F2BDDD8B-C2CF-4EA6-A4FB-30CE94527926","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"02632a2d4cf50e9c1e88f5bb597249e6b4d29ae9","datavalue":{"value":"The paper of \\textit{M. Sudan} [J. Complexity 13, No. 1, 180--193 (1997; Zbl 0872.68026)] introduced a new paradigm in the decoding of error-correcting codes: the list decoding. First formulated for Reed-Solomon codes, the papers of \\textit{M. A. Shokrollahi} and \\textit{H. Wasserman} [IEEE Trans. Inf. Theory 45, No. 2, 432--437 (1999; Zbl 0947.94024)] and \\textit{V. Guruswami} and \\textit{M. Sudan} [IEEE Trans. Inf. Theory 45, No. 6, 1757--1767 (1999; Zbl 0958.94036)] extended the algorithm of Sudan to algebraic-geometry (AG) codes.  The central and more costly step in the algorithm of Guruswami and Sudan is an interpolation step. The present paper proposes an efficient interpolation algorithm for a certain class of AG codes.  Section 2 introduces the family of AG codes that are considered in the remainder of the paper, the family of one-point AG codes that includes Reed-Solomon codes, Hermitian codes and norm-trace codes. Section 3 reformulates the constrained interpolation problem in the algorithm of Guruswami and Sudan in terms of finitely generated modules over an univariate polynomial ring. In this formulation interpolation polynomials of low degree correspond to short vectors in the module.  To find such short vectors, Section 4 generalizes an algorithm due to \\textit{M. Alekhnovich} [``Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes'', IEEE Trans. Inf. Theory 51, No. 7, 2257--2265 (2005)] and Section 5 shows that this algorithm can compute the necessary interpolation polynomial. Finally, Section 6 examines several examples of codes in the family (projective line, elliptic codes, Hermitian codes), finding for each of them the complexity of the interpolation step, a complexity that it is lower than the complexity of previously known algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q540394$A6FB30A0-FBCB-4322-873E-DB6C1A39EBB3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4430c94528f7856126af01b3ac6ccc7f8c77602b","datavalue":{"value":"94B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540394$6F18BA28-F384-4A44-A900-568F3D32BD27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dcefd1e200eae54420c5080733f6b5a349da9f6a","datavalue":{"value":"11T71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540394$D440C8D1-1A54-4A66-9F44-006EEB1ADE9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"332a7ca0fc2503044cbe5299ecaa975484163791","datavalue":{"value":"14G50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540394$C1737309-E1C2-4240-8E67-D99A10AE2A8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5120626c87fbc492ba1414fde6695c15d7ff0d86","datavalue":{"value":"94B27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540394$F24BF824-D48B-4DCA-A31C-83EBE4E62A6F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9912add4ce0de47dfb7b6b38ea0272be11583a78","datavalue":{"value":"5903544","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540394$49AB05B6-0CBD-491C-A103-F2F089B7A5CD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a0fbcbda315d7c36fb3db7e2021d5bcd2697a38","datavalue":{"value":"list decoding","type":"string"},"datatype":"string"},"type":"statement","id":"Q540394$F2DC3F2A-3A78-46E5-AA77-1F4C0DC5325A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94704f32b83c8a1a07d298b1ae968964460d3229","datavalue":{"value":"algebraic-geometry codes","type":"string"},"datatype":"string"},"type":"statement","id":"Q540394$491555F0-A962-4B34-A36B-46292CA4E34E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f076287b1464eddb014eed00691bc7e421e62eee","datavalue":{"value":"interpolation step","type":"string"},"datatype":"string"},"type":"statement","id":"Q540394$30053DCC-85B9-4BBB-9B2D-30A91B021F23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d65d18fcc80a3cb1366b661a1e75b00d2eb00754","datavalue":{"value":"Alekhnovich's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q540394$8ABEF984-53C0-4A66-8A20-6012661151CB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8892955fafe16ba1bddb104e5d82ec8889d70fd9","datavalue":{"value":{"entity-type":"item","numeric-id":1313210,"id":"Q1313210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540394$CFEC90C3-49FE-4AC9-A78E-66C01A9F641F","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4fe03e5b78d9974ebdfc0233dbd377f30d5d075f","datavalue":{"value":{"entity-type":"item","numeric-id":13295,"id":"Q13295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540394$3F7141F0-6F34-4ABD-8226-62E77BB70CB7","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":"Q540394$38AB5F29-09B2-4412-A6BD-3533F437BEF1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ac41d0617f1cd8938eab8ed7f7eca81832717c13","datavalue":{"value":"https://doi.org/10.3934/amc.2010.4.485","type":"string"},"datatype":"url"},"type":"statement","id":"Q540394$B7E422E1-9155-41DB-817C-71669CB912FC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"11e783b7fb76aad9e73fa04dba4ae0ffd5a7e55d","datavalue":{"value":"W2009890571","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540394$01854D9A-D43D-461F-AB70-2FF44DA18050","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1615c59bde3e0fdaa49be384a3b96db3c03dd1d4","datavalue":{"value":"10.3934/AMC.2010.4.485","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540394$67385B45-E8D1-4FC0-BFBD-2C03D200801F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08b67f90eca4b021b550cb41636a3d6dd108883a","datavalue":{"value":{"entity-type":"item","numeric-id":4474234,"id":"Q4474234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03b25c26c9a35b7e4bc4518c7a97a3db08aad915","datavalue":{"value":{"amount":"+0.885238","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540394$45CF61BB-55D6-4436-9088-BAEE201B9218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77340b3f83cd3ada0288110de5abae5ec92c9fbf","datavalue":{"value":{"entity-type":"item","numeric-id":4701292,"id":"Q4701292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16ed461abe5ce2c0e2f972f74095e9967242c837","datavalue":{"value":{"amount":"+0.8803754","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540394$3670D1C6-D7CC-4CBD-95C7-84F93C7AD24C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f90cbac8af9e3ce260b8803406ee183ac1ccc2e","datavalue":{"value":{"entity-type":"item","numeric-id":4474252,"id":"Q4474252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0630587a3d228bd2a7112672fdfe16ba78b89fbf","datavalue":{"value":{"amount":"+0.8775364","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540394$E4CAC03B-5823-4821-8343-DEE2F8CEA532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49898d01d3b1bb7eab8df9d4fb7902436d9b1d8d","datavalue":{"value":{"entity-type":"item","numeric-id":2705986,"id":"Q2705986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f51976d918291fd6f6c582be0bca1f2fa637cb66","datavalue":{"value":{"amount":"+0.8600086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540394$3136B509-2588-48A4-927B-DAF5ACFC21F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b56ad9e9e24ce6e80d4e1cd824634a65166a08c6","datavalue":{"value":{"entity-type":"item","numeric-id":4503371,"id":"Q4503371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c169fc7428143797624986df667bb8b6507c2dd9","datavalue":{"value":{"amount":"+0.85673374","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540394$5B15701F-C42C-4062-94B3-17BAE24CF63C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbc8d0f57157cd9e77191556065c18be816a4f7d","datavalue":{"value":{"entity-type":"item","numeric-id":931140,"id":"Q931140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"540d5309690f8991884ced709b5e5f924d3e5ec1","datavalue":{"value":{"amount":"+0.85449404","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540394$C90046B0-3DAF-4E5C-8388-F955A8B8CC0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b61bdd3dfbcec8f31a81324deaf9bcabb74212b","datavalue":{"value":{"entity-type":"item","numeric-id":661987,"id":"Q661987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"141165925040ccd4d1e4e7186ca1e48736482f4a","datavalue":{"value":{"amount":"+0.8495538","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540394$54483E3B-C190-42D1-AB13-03B7E49AEE7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3fee8e19692d0cffe90b90f0e4553f6a3d931db","datavalue":{"value":{"entity-type":"item","numeric-id":2819550,"id":"Q2819550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d50b403ac16ddc6970551cf8f9c1073202342713","datavalue":{"value":{"amount":"+0.84941375","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540394$0709742A-9955-4A4D-8006-C4E9D91191F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d16ce4db31f29caf490d781ec4bcb4c77ff8eb29","datavalue":{"value":{"entity-type":"item","numeric-id":2460910,"id":"Q2460910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"557ad189b6d7f8a57ab147ea95e78bd46b605bdd","datavalue":{"value":{"amount":"+0.84826887","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540394$F011FBCC-B5DC-41A8-86A2-A2EC9F17B2C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e146db115d20e128106224b129811e26b0f42b6","datavalue":{"value":{"entity-type":"item","numeric-id":4544702,"id":"Q4544702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e06dce009c8f21e2c1328af0eeb71c99174a3b1","datavalue":{"value":{"amount":"+0.83884674","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540394$33FC7DEB-87DD-4262-A33C-D7EFFC40526C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient list decoding of a class of algebraic-geometry codes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_list_decoding_of_a_class_of_algebraic-geometry_codes"}}}}}