---
_id: '11145'
abstract:
- lang: eng
  text: List-decodability of Reed-Solomon codes has re-ceived a lot of attention,
    but the best-possible dependence between the parameters is still not well-understood.
    In this work, we focus on the case where the list-decoding radius is of the form
    r=1−ε for ε tending to zero. Our main result states that there exist Reed-Solomon
    codes with rate Ω(ε) which are (1−ε,O(1/ε) -list-decodable, meaning that any Hamming
    ball of radius 1−ε contains at most O(1/ε) codewords. This trade-off between rate
    and list-decoding radius is best-possible for any code with list size less than
    exponential in the block length. By achieving this trade-off between rate and
    list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and
    Wootters, and resolve the main motivating question of their work. Moreover, while
    their result requires the field to be exponentially large in the block length,
    we only need the field size to be polynomially large (and in fact, almost-linear
    suffices). We deduce our main result from a more general theorem, in which we
    prove good list-decodability properties of random puncturings of any given code
    with very large distance.
article_processing_charge: No
arxiv: 1
author:
- first_name: Asaf
  full_name: Ferber, Asaf
  last_name: Ferber
- first_name: Matthew Alan
  full_name: Kwan, Matthew Alan
  id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
  last_name: Kwan
  orcid: 0000-0002-4003-7567
- first_name: Lisa
  full_name: Sauermann, Lisa
  last_name: Sauermann
citation:
  ama: 'Ferber A, Kwan MA, Sauermann L. List-decodability with large radius for Reed-Solomon
    codes. In: <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i>.
    Vol 2022. IEEE; 2022:720-726. doi:<a href="https://doi.org/10.1109/FOCS52979.2021.00075">10.1109/FOCS52979.2021.00075</a>'
  apa: 'Ferber, A., Kwan, M. A., &#38; Sauermann, L. (2022). List-decodability with
    large radius for Reed-Solomon codes. In <i>62nd Annual IEEE Symposium on Foundations
    of Computer Science</i> (Vol. 2022, pp. 720–726). Denver, CO, United States: IEEE.
    <a href="https://doi.org/10.1109/FOCS52979.2021.00075">https://doi.org/10.1109/FOCS52979.2021.00075</a>'
  chicago: Ferber, Asaf, Matthew Alan Kwan, and Lisa Sauermann. “List-Decodability
    with Large Radius for Reed-Solomon Codes.” In <i>62nd Annual IEEE Symposium on
    Foundations of Computer Science</i>, 2022:720–26. IEEE, 2022. <a href="https://doi.org/10.1109/FOCS52979.2021.00075">https://doi.org/10.1109/FOCS52979.2021.00075</a>.
  ieee: A. Ferber, M. A. Kwan, and L. Sauermann, “List-decodability with large radius
    for Reed-Solomon codes,” in <i>62nd Annual IEEE Symposium on Foundations of Computer
    Science</i>, Denver, CO, United States, 2022, vol. 2022, pp. 720–726.
  ista: 'Ferber A, Kwan MA, Sauermann L. 2022. List-decodability with large radius
    for Reed-Solomon codes. 62nd Annual IEEE Symposium on Foundations of Computer
    Science. FOCS: Symposium on Foundations of Computer Science vol. 2022, 720–726.'
  mla: Ferber, Asaf, et al. “List-Decodability with Large Radius for Reed-Solomon
    Codes.” <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i>,
    vol. 2022, IEEE, 2022, pp. 720–26, doi:<a href="https://doi.org/10.1109/FOCS52979.2021.00075">10.1109/FOCS52979.2021.00075</a>.
  short: A. Ferber, M.A. Kwan, L. Sauermann, in:, 62nd Annual IEEE Symposium on Foundations
    of Computer Science, IEEE, 2022, pp. 720–726.
conference:
  end_date: 2022-02-10
  location: Denver, CO, United States
  name: 'FOCS: Symposium on Foundations of Computer Science'
  start_date: 2022-02-07
date_created: 2022-04-10T22:01:40Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2023-08-03T06:57:02Z
day: '01'
department:
- _id: MaKw
doi: 10.1109/FOCS52979.2021.00075
external_id:
  arxiv:
  - '2012.10584'
  isi:
  - '000802209600065'
intvolume: '      2022'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.2012.10584'
month: '02'
oa: 1
oa_version: Preprint
page: 720-726
publication: 62nd Annual IEEE Symposium on Foundations of Computer Science
publication_identifier:
  isbn:
  - '9781665420556'
  issn:
  - 0272-5428
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
  record:
  - id: '10775'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: List-decodability with large radius for Reed-Solomon codes
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 2022
year: '2022'
...