{"id":2133,"date":"2021-10-20T11:12:27","date_gmt":"2021-10-20T08:12:27","guid":{"rendered":"https:\/\/mathematics.haifa.ac.il\/?p=2133"},"modified":"2021-11-04T12:17:17","modified_gmt":"2021-11-04T10:17:17","slug":"colloquium-tuesday-october-26-2021-speaker-jonathan-mosheiff-carnegie-mellon-university-title-derandomization-of-elementary-error-correcting-code-ensembles","status":"publish","type":"post","link":"https:\/\/mathematics.haifa.ac.il\/?p=2133","title":{"rendered":"Colloquium: Tuesday, October 26, 2021. Speaker: Jonathan Mosheiff (Carnegie Mellon University). Title: &#8220;Derandomization of elementary error correcting code ensembles&#8221;."},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><strong>Zoom link:&nbsp;<\/strong><a rel=\"noreferrer noopener\" href=\"https:\/\/us02web.zoom.us\/j\/82797905845?pwd=VUxHdkwyRzZIOHdDWkF2OC92U0p6UT09\" target=\"_blank\">https:\/\/us02web.zoom.us\/j\/82797905845?pwd=VUxHdkwyRzZIOHdDWkF2OC92U0p6UT09<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">An error correcting code is a subset C of F_q^n. We usually want C to be 1) large, 2) well-spread and 3) efficiently decodable. Elementary random constructions, such as taking C to be a uniformly random linear subspace of the ambient vector space, achieve a very good trade-off between the first two desiderata, but are not amenable to algorithms. This motivates us to derandomize these constructions in a way that preserves spreadness, while adding some structure that can be used for algorithmic purposes. We discuss this line of research, focusing on two results.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">1) In many settings, such as the ubiquitous model of list-decoding, the spreadness of a code can be formulated as a local and symmetric property. We show that such properties exhibit a certain threshold behavior with regard to random linear codes, in analogy to classic results about local properties of random graphs. This provides us with a framework by which to prove the spreadness of other code ensembles via reduction to the random linear code ensemble. We use such a reduction to prove that random LDPC codes are combinatorially list-decodable up to capacity (i.e., optimally).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">2) A random linear code can be interpreted as the output of a random puncturing operation applied to the Hadamard code. The latter is a certain code of optimal distance. We prove that, much more generally, a random puncturing of any code of near-optimal distance is likely to be essentially as well-spread as a random linear code. Consequently, by a further reduction, we show that many Reed-Solomon codes are list-decodable up to capacity.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Based on joint works with Venkatesan Guruswami, Ray Li, Nati Linial, Peter Manohar, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas and Mary Wootters.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Zoom link:&nbsp;https:\/\/us02web.zoom.us\/j\/82797905845?pwd=VUxHdkwyRzZIOHdDWkF2OC92U0p6UT09 An error correcting code is a subset C of F_q^n. We usually want C to be 1) large, 2) well-spread and 3) efficiently decodable. Elementary random constructions, such as taking C to be a uniformly random linear subspace&#8230;<br \/><a class=\"read-more-button\" href=\"https:\/\/mathematics.haifa.ac.il\/?p=2133\">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-2133","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\/2133","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=2133"}],"version-history":[{"count":2,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts\/2133\/revisions"}],"predecessor-version":[{"id":2135,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts\/2133\/revisions\/2135"}],"wp:attachment":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2133"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2133"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2133"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}