Plenary Speakers

Sergei Vassilvitskii
Google New York

Using Predictions for Better Approximations 

The design of efficient algorithms often hinges on worst-case analysis, yet real-world scenarios frequently exhibit predictable patterns. In this talk we will explore the rapidly evolving field of Algorithms with Predictions, a paradigm that seeks to leverage imperfect predictions to achieve performance beyond what's possible under strict worst-case guarantees, while still maintaining provable robustness when predictions are inaccurate. We will give examples showing how predictions can be integrated into classic algorithmic problems and address the core challenge --- balancing the gains from accurate predictions with the resilience needed against erroneous ones. The aim is to bridge the gap between theoretical optimality and practical effectiveness, opening new avenues for algorithm design in data-rich environments.

Venkatesan Guruswami
Simons Institute for the Theory of Computing and UC Berkeley

A few options go a long way: List decoding and its many applications

List decoding relaxes traditional error correction by allowing the decoder to output a small list of candidate codewords, succeeding as long as the original message is among them. Though this compromise may seem modest, it has led to a rich and far-reaching theory.

List decoding bridges the classical divide between the Hamming and Shannon models, enabling capacity-achieving codes even against worst-case errors. It underpins versatile error-correction subroutines and inspires constructions and algorithms far beyond its initial scope. Its influence extends to a number of "extraneous" applications in pseudorandomness, computational complexity, cryptography, and quantum computing. Along the way, it has introduced novel algebraic, probabilistic, and combinatorial techniques into coding theory.

This talk will offer a glimpse into the many facets of list decoding—its origins, evolution, constructions, connections, and wide-ranging applications.