Select Page

# Highlights of Algorithmic Coding Theory by Madhu Sudan from Harvard University

BGSMath Course
From May 06, 2024
to May 08, 2024

Registration is free but mandatory through the SIGN-IN button

* Please note that seats are limited, participants will receive the final info by May 1, 2024.

LOCATION: Facultat de Matemàtiques de la Universitat de Barcelona - Room T1

SCHEDULE: May 6, 7 and 8 from 11h to 13h (45' + break + 45')

Registration deadline 30 / 04 / 2024

Introduction

In this series of lectures, we will quickly introduce the mathemtical notions of an error-correcting code, and the associated notions of Encoding and Decoding Algorithms. After reviewing some of the classical results on the existence, construction and limits on error-correcting codes, we will zoom in on two results in the field.

1) The construction of capacity achieving codes (based on Folded Reed Solomon Codes) over large alphabets and their encoding and decoding:Given any error parameter delta in [0,1] and epsilon > 0, these codes achieve a rate 1-delta-epsilon and correct delta fraction of adversarial errors with alphabet size growing only with epsilon.2) The construction of binary error correcting codes (Polar codes) that achieve Shannon capacity at small block lengths: I.e, given delta in [0,1/2] and epsilon > 0 correct delta fraction of random errors with rate 1- h(delta) – epsilon at lengths poly(1/epsilon). [Here h(p) = -plog_2 p – (1-p) log_2 (1-p) is the binary entropy function].

Both results come with polynomial time algorithms!

SPEAKER

##### Harvard University

Madhu Sudan is a Gordon McKay Professor in the John A. Paulson School of Engineering and Applied Sciences at Harvard University, where he has been since 2015. Madhu got his Bachelor’s degree from IIT Delhi in 1987, and his PhD from UC Berkeley in 1992. From 1992 to 2015, Madhu worked at IBM Research (Research Staff Member 1992-1997), at MIT (Associate Professor 1997-2000, Professor 2000-2011, Fujitsu Chair Professor 2003-2011, CSAIL Associate Director 2007-2009, Adjunct Professor 2011-2015), and at Microsoft Research (Principal Researcher, 2009-2015). He is a recipient of the Nevanlinna Prize awarded by the International Mathematical Union for outstanding contributions to mathematics of computer and information science, and the Infosys Foundation Prize in Mathematical Sciences. Madhu is also a fellow of the Association for Computing Machinery, the Institute of Electrical and Electronics Engineers and the American Mathematical Society. Additionally, he is a member of the American Academy of Arts and Sciences and the National Academy of Sciences.

Madhu’s research interests revolve around mathematical studies of communication and computation. Specifically, his research focuses on concepts of reliability and mechanisms that are, or can be, used by computers to interact reliably with each other. His research draws on tools from computational complexity, which studies efficiency of computation, and many areas of mathematics including algebra and probability theory. He is best known for his works on probabilistic checking of proofs, and on the design of list-decoding algorithms for error-correcting codes. His current research interests include property testing—which is the study of sublinear time algorithms to estimate properties of massive data, and communication amid uncertainty—a mathematical study of the role of context in communication.

LIST OF PARTICIPANTS

Name Institution
Swarnadeep Choudhury Tripura University (A Central University)
Pau Soler Valadés Universitat de Barcelona
Xavier Guitart Universitat de Barcelona
Noelia Sánchez Universitat de Barcelona
Sergi Sánchez Aragón Universitat Autònoma de Barcelona
Dipak Kumar Bhunia Universitat Autònoma de Barcelona
Guillem Perarnau Llobet Universitat Politècnica de Catalunya
Clément Requilé Universitat Politècnica de Catalunya
Lucas Bazilio Universitat Politècnica de Catalunya
Cristian Sánchez Universitat Politècnica de Catalunya
Adrià Lisa Bou Universitat Politècnica de Catalunya
Antoni Burón i Palau Universitat Politècnica de Catalunya
Xavier Povill Universitat Politècnica de Catalunya
Oriol Serra Albó Universitat Politècnica de Catalunya
Conrado Martínez Universitat Politècnica de Catalunya
Albert Atserias Universitat Politècnica de Catalunya
Félix Moreno Peñarrubia Universitat Politècnica de Catalunya
Sofiya Burova Universitat Politècnica de Catalunya
María Lucia Aparicio García Universitat Politècnica de Catalunya
Simeon Ball Universitat Politècnica de Catalunya
Elena Isasi Theus Universitat Politècnica de Catalunya
Tabriz Popatia Universitat Politècnica de Catalunya
Fernando Gastón Codony Universitat Politècnica de Catalunya
Georgios Karelas Universitat Pompeu Fabra
Maxim Fedotov Universitat Pompeu Fabra
Ahana Deb Universitat Pompeu Fabra
Ignacio Fernández Rúa Universidad de Oviedo
José Juan Peña Leal National Autonomous University of Mexico
Álvaro Ribot Barrado Harvard University
Mariona Montserrat Fucho Rius Centre de Recerca Matemàtica
Pau Reig Llunell Centre de Recerca Matemàtica
Marcel Morillas Rozas Centre de Recerca Matemàtica
Andrea Suárez Segarra Centre de Recerca Matemàtica

related activities – CRM COLLOQUIUM by Madhu Sudan – May 9, 2024 at IEC

Abstract

#### Mathematical Theories of Communication: Old and New

Reliable and efficient digital communication is possible today largely due to some wonderful successes in mathematical modelling and analysis. A legendary figure in this space is Claude Shannon (1916-2001) who laid out the mathematical foundations of communication in his seminal 1948 treatise, where among other contributions he gave a mathematical definition of “entropy” and coined the now ubiquitous term “bit” (for binary digit). But Shannon’s theory is not the last word in communication. Communication extends to settings well beyond the carefully designed full information exchange model explored in Shannon’s work. In this talk I will try to describe some of the many extensions that have been explored in the interim period including communication complexity (Yao 1980) that explores how it might be possible to achieve effective communication without a full exchange; interactive communication (Schulman 1992) which explores how to cope with errors in an interactive setting, and some of our own work on uncertain communication, which explores how shared context can make communication more effective, even if the context is shared only loosely.

CRM Colloquium