[{"ddc":["510","000"],"language":[{"iso":"eng"}],"article_number":"82","day":"11","scopus_import":"1","conference":{"location":"New York, NY, United States","start_date":"2025-01-07","end_date":"2025-01-10","name":"ITCS: Innovations in Theoretical Computer Science"},"status":"public","arxiv":1,"OA_type":"gold","date_created":"2025-03-02T23:01:53Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":325,"external_id":{"isi":["001532717300082"],"arxiv":["2309.01800"]},"intvolume":"       325","alternative_title":["LIPIcs"],"publication":"16th Innovations in Theoretical Computer Science Conference","file_date_updated":"2025-03-04T09:35:57Z","title":"Tight bounds on list-decodable and list-recoverable zero-rate codes","date_updated":"2025-09-30T10:42:35Z","doi":"10.4230/LIPIcs.ITCS.2025.82","corr_author":"1","OA_place":"publisher","file":[{"file_id":"19286","file_size":898601,"file_name":"2025_LIPIcs_Resch.pdf","relation":"main_file","date_created":"2025-03-04T09:35:57Z","checksum":"df3921ddf1b360b07f43d427fea51242","date_updated":"2025-03-04T09:35:57Z","access_level":"open_access","creator":"dernst","success":1,"content_type":"application/pdf"}],"department":[{"_id":"MaMo"}],"citation":{"ama":"Resch N, Yuan C, Zhang Y. Tight bounds on list-decodable and list-recoverable zero-rate codes. In: <i>16th Innovations in Theoretical Computer Science Conference</i>. Vol 325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.82\">10.4230/LIPIcs.ITCS.2025.82</a>","mla":"Resch, Nicolas, et al. “Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes.” <i>16th Innovations in Theoretical Computer Science Conference</i>, vol. 325, 82, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.82\">10.4230/LIPIcs.ITCS.2025.82</a>.","apa":"Resch, N., Yuan, C., &#38; Zhang, Y. (2025). Tight bounds on list-decodable and list-recoverable zero-rate codes. In <i>16th Innovations in Theoretical Computer Science Conference</i> (Vol. 325). New York, NY, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.82\">https://doi.org/10.4230/LIPIcs.ITCS.2025.82</a>","short":"N. Resch, C. Yuan, Y. Zhang, in:, 16th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ista":"Resch N, Yuan C, Zhang Y. 2025. Tight bounds on list-decodable and list-recoverable zero-rate codes. 16th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 325, 82.","chicago":"Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes.” In <i>16th Innovations in Theoretical Computer Science Conference</i>, Vol. 325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.82\">https://doi.org/10.4230/LIPIcs.ITCS.2025.82</a>.","ieee":"N. Resch, C. Yuan, and Y. Zhang, “Tight bounds on list-decodable and list-recoverable zero-rate codes,” in <i>16th Innovations in Theoretical Computer Science Conference</i>, New York, NY, United States, 2025, vol. 325."},"date_published":"2025-02-11T00:00:00Z","_id":"19281","has_accepted_license":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_status":"published","month":"02","oa_version":"Published Version","type":"conference","license":"https://creativecommons.org/licenses/by/4.0/","quality_controlled":"1","year":"2025","acknowledgement":"The research of C. Yuan was support in part by the National Key R&D Program of China\r\nunder Grant 2023YFE0123900 and Natural Science Foundation of Shanghai under the 2024 Shanghai Action Plan for Science, Technology and Innovation Grant 24BC3200700. The research of N. Resch is supported in part by an NWO (Dutch Research Council) grant with number C.2324.0590, and this work was done in part while he was visiting the Simons Institute for the Theory of Computing, supported by DOE grant #DE-SC0024124.","oa":1,"author":[{"full_name":"Resch, Nicolas","last_name":"Resch","first_name":"Nicolas"},{"last_name":"Yuan","first_name":"Chen","full_name":"Yuan, Chen"},{"first_name":"Yihan","last_name":"Zhang","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan","orcid":"0000-0002-6465-6258"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"abstract":[{"text":"In this work, we consider the list-decodability and list-recoverability of codes in the zero-rate regime. Briefly, a code 𝒞 ⊆ [q]ⁿ is (p,𝓁,L)-list-recoverable if for all tuples of input lists (Y₁,… ,Y_n) with each Y_i ⊆ [q] and |Y_i| = 𝓁, the number of codewords c ∈ 𝒞 such that c_i ∉ Y_i for at most pn choices of i ∈ [n] is less than L; list-decoding is the special case of 𝓁 = 1. In recent work by Resch, Yuan and Zhang (ICALP 2023) the zero-rate threshold for list-recovery was determined for all parameters: that is, the work explicitly computes p_*: = p_*(q,𝓁,L) with the property that for all ε > 0 (a) there exist positive-rate (p_*-ε,𝓁,L)-list-recoverable codes, and (b) any (p_*+ε,𝓁,L)-list-recoverable code has rate 0. In fact, in the latter case the code has constant size, independent on n. However, the constant size in their work is quite large in 1/ε, at least |𝒞| ≥ (1/(ε))^O(q^L).\r\nOur contribution in this work is to show that for all choices of q,𝓁 and L with q ≥ 3, any (p_*+ε,𝓁,L)-list-recoverable code must have size O_{q,𝓁,L}(1/ε), and furthermore this upper bound is complemented by a matching lower bound Ω_{q,𝓁,L}(1/ε). This greatly generalizes work by Alon, Bukh and Polyanskiy (IEEE Trans. Inf. Theory 2018) which focused only on the case of binary alphabet (and thus necessarily only list-decoding). We remark that we can in fact recover the same result for q = 2 and even L, as obtained by Alon, Bukh and Polyanskiy: we thus strictly generalize their work. \r\nOur main technical contribution is to (a) properly define a linear programming relaxation of the list-recovery condition over large alphabets; and (b) to demonstrate that a certain function defined on a q-ary probability simplex is maximized by the uniform distribution. This represents the core challenge in generalizing to larger q (as a binary simplex can be naturally identified with a one-dimensional interval). We can subsequently re-utilize certain Schur convexity and convexity properties established for a related function by Resch, Yuan and Zhang along with ideas of Alon, Bukh and Polyanskiy.","lang":"eng"}],"article_processing_charge":"Yes","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773614"]},"isi":1}]