{"id":2993,"date":"2025-05-22T10:26:30","date_gmt":"2025-05-22T07:26:30","guid":{"rendered":"https:\/\/mathematics.haifa.ac.il\/?p=2993"},"modified":"2025-06-12T11:15:07","modified_gmt":"2025-06-12T08:15:07","slug":"colloquium-tuesday-may-27-2025-speaker-sergey-komech-ben-gurion-title-optimal-list-recoverability-via-alphabet-permutation-codes","status":"publish","type":"post","link":"https:\/\/mathematics.haifa.ac.il\/?p=2993","title":{"rendered":"Colloquium: Tuesday May 27, 2025. Speaker: Sergey Komech (Ben Gurion). Title: &#8220;Optimal list-recoverability via alphabet permutation codes&#8221;."},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><strong>Speaker:<\/strong>&nbsp;Sergey Komech (Ben Gurion)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Place:&nbsp;<\/strong>Room 614, Education and Sciences Building, University of Haifa<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Date and Time:<\/strong>&nbsp;May 20, 2025, 14:00-15:00<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Title:&nbsp;<\/strong><em>Optimal list-recoverability via alphabet permutation codes<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Abstract<\/strong><strong>:&nbsp;<\/strong>See attached PDF.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Zoom link:&nbsp;<\/strong><a href=\"https:\/\/us02web.zoom.us\/j\/87282501214?pwd=gnoO4TOG9LKBQJrfQ89Od7nUkoy0S3.1\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/us02web.zoom.us\/j\/87282501214?pwd=gnoO4TOG9LKBQJrfQ89Od7nUkoy0S3.1<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Meeting ID: 872 8250 1214<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Passcode: 009572<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">A basic problem in the Coding theory is to transfer information over a noisy channel so that the original codeword can be recovered from the received word that can have some bits corrupted by noise. List-decoding and list-recovery are generalizations of unique decoding, when it is allowed for a receiver to recover a list of words that should contain the original codeword. List-recovery is more general, and it has been studied less than list-decoding.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">It is known that list-recovery with non-exponential list size is possible if the rate of a code is $R = 1 &#8211; h_{q,\\ell}(\\rho) &#8211; \\varepsilon$, where $h_{q,\\ell}(\\cdot)$ is the $(q,\\ell)$-\\textit{ary entropy}.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">{\\it Elias Bound} for list-recovery is presented by the list size $L = O\\,(\\frac{\\ell}{\\varepsilon})$, which is achieved by Plain Random Codes (PRC). PRC hit the desired list size, but they need exponential randomness to be described.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">We construct a new family of codes that requires only polynomial randomness yet achieves $(\\rho,\\ell,L)$-list-recoverability at the aforementioned rate, with list size $L \\approx \\frac{\\ell}{\\varepsilon}$. In contrast, every previous construction using polynomial randomness requires an exponentially larger list size. Our approach extends earlier work by Li and Wootters (2021) on the list-decodability of random linear binary codes.<br>Joint work with Jonathan Mosheiff.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Speaker:&nbsp;Sergey Komech (Ben Gurion) Place:&nbsp;Room 614, Education and Sciences Building, University of Haifa Date and Time:&nbsp;May 20, 2025, 14:00-15:00 Title:&nbsp;Optimal list-recoverability via alphabet permutation codes Abstract:&nbsp;See attached PDF. Zoom link:&nbsp;https:\/\/us02web.zoom.us\/j\/87282501214?pwd=gnoO4TOG9LKBQJrfQ89Od7nUkoy0S3.1 Meeting ID: 872 8250 1214 Passcode: 009572 A basic problem&#8230;<br \/><a class=\"read-more-button\" href=\"https:\/\/mathematics.haifa.ac.il\/?p=2993\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-2993","post","type-post","status-publish","format-standard","hentry","category-colloquium"],"_links":{"self":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts\/2993","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2993"}],"version-history":[{"count":2,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts\/2993\/revisions"}],"predecessor-version":[{"id":2996,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts\/2993\/revisions\/2996"}],"wp:attachment":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2993"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2993"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2993"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}