03/09/2026
𝗖𝗢𝗟Ó𝗤𝗨𝗜𝗢 𝗗𝗘 𝗠𝗔𝗧𝗘𝗠Á𝗧𝗜𝗖𝗔
𝗣𝗮𝗰𝗸𝗶𝗻𝗴 𝗼𝗿𝗮𝗻𝗴𝗲𝘀 𝗮𝘁 𝗿𝗮𝗻𝗱𝗼𝗺
𝗝𝗼ã𝗼 𝗥𝗶𝗯𝗲𝗶𝗿𝗼
𝟯𝟬 𝘀𝗲𝘁 | 𝟭𝟲:𝟬𝟬 | 𝟲.𝟮.𝟯𝟯
Abstract: The classical sphere packing problem in n dimensions asks what is the largest fraction of R^n that can be covered by non-overlapping spheres all of equal radius. Variants of this problem can be posed in other spaces (such as F_q^n, with F_q the finite field of order q) with respect to any metric. In particular, this turns out to capture the design of optimal error-correcting codes for reliable communication over noisy channels, making things like phone calls, deep space communication, video streaming, data storage, and the Internet possible at large scales.
Curiously, we often get good packings by cramming spheres into a space "uniformly at random". This leads to some basic questions in coding theory: Can we "derandomize" this uniformly random packing, achieving the same density using less or even no randomness? And can we beat uniformly random packing?
I will give an overview of the history surrounding these questions, including some recent results obtained jointly with Roni Con, Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, and Nicolas Resch. The talk will assume no background beyond familiarity with basic algebra, counting, and discrete probability.
Bio: João is an assistant professor in the Math Department at IST-UL and a researcher at Instituto de Telecomunicações, where he is the principal investigator of the ERC Starting Grant Limits and Efficiency of Coding Against Synchronization Errors. Previously, he was an assistant professor in the CS Department at Universidade Nova de Lisboa. Previously, he was a postdoctoral fellow in the CS Department at Carnegie Mellon University, hosted jointly by Vipul Goyal and Venkatesan Guruswami. Even before that, he did his PhD in the Department of Computing at Imperial College London, where he was advised by Mahdi Cheraghchi.
