Seminar ACR lab-VIASM

Time:

Venue/Location: Phòng C101, VIASM

Báo cáo viên: Phuoc Van Long Pham (Brown University, USA)  

Đề tài: Survey for Reed-Solomon List Decoding and related topics 

Tóm tắt: Since the Stone Age, people have already known that any polynomial of degree d has at most d real solutions, but over finite fields, everything is still chaos. It takes a long time until the Age of Enlightenment, that Lagrange sets his first steps onto the land of finite fields with his theorem, stating that a polynomial of degree d over any finite field still has at most d roots (Lagrange does not even know what is finite field at the time!). Building on this crucial property of polynomials, Irving Reed and Gustave Solomon bring its influence from number theory all the way to information theory, by inventing the Reed-Solomon code. They also did not know at the time that this code became so influential in a field called Zero Knowledge Proofs, especially its list decoding property. Most parameter regimes for list decoding have been explored, by famous algorithms from Berlekamp-Welch to Guruswami-Sudan, but there is still one unknown range, that is from the Johnson Bound 1-\sqrt{R} to the code capacity 1-R. This talk acts as a small survey to introduce the techniques of these algorithms, and also introduce the list decoding (open) problem beyond the Johnson bound. There also happens to have a prize tag by the Ethereum Foundation for solving it. 

Zoom: https://zoom.us/j/93460558155?pwd=qZadAJtXO9O1P5bf9eCblb6dcWI3pJ.1 

           Meeting ID: 934 6055 8155

            Passcode: 582204