קולוקוויום וסמינרים

Linear error‑correcting codes that handle insertions and deletions (indels) are fundamental to reliable storage and communication in settings where symbol positions may drift—from DNA data storage to packet‑based networks. Unlike substitution and erasure errors, indels disrupt sequence alignment and therefore require additional synchronization information.

This talk surveys recent constructive techniques that embed such synchronization within fully linear codes, preserving algebraic structure while supporting efficient encoding and decoding. We explain how short synchronization sequences can be interleaved with algebraic‑geometry codes to form “half‑linear” indel codes, and how a padding–flattening procedure converts them into fully linear codes over the base field with only a modest rate penalty. A decoder that combines longest‑common‑subsequence matching with asymmetric Hamming decoding then corrects a prescribed fraction of indels in polynomial time.

Along the way we discuss a subfield‑Singleton–style limitation that shows why rate 1/2 cannot be surpassed—even for a single indel—when only base‑field linearity is assumed. The resulting framework narrows the gap between known lower and upper bounds for linear indel codes and suggests new directions—including tighter synchronization primitives and improved high‑rate constructions—for bringing practical, algebraically structured indel correction closer to theoretical limits.

We introduce a Probably Approximately Correct (PAC) learning framework where each hypothesis is represented by a graph, with edges indicating positive interactions, such as between users and items. This framework subsumes the classical binary and multi-class PAC learning models as well as multi-label learning with partial feedback, where only a single random correct label per example is observed, rather than all correct labels.

Our work uncovers a rich statistical and algorithmic landscape, with nuanced boundaries on what can and cannot be learned. Notably, classical methods like Empirical Risk Minimization fail in this setting, even for simple hypothesis classes with only two hypotheses. To address these challenges, we develop novel algorithms that learn exclusively from positive data, effectively minimizing both precision and recall losses. Specifically, in the realizable setting, we design algorithms that achieve optimal sample complexity guarantees. In the agnostic case, we show that it is impossible to achieve additive error guarantees (i.e., additive regret)—as is standard in PAC learning—and instead obtain meaningful multiplicative approximations.

I will describe several old and new applications of topological and algebraic methods in the derivation of combinatorial results. In all of them the proofs provide no efficient procedures for solving the corresponding algorithmic questions. The problem of finding such procedures (or convincing reasons indicating that they are unlikely to exist) is an intriguing challenge and I will mention some progress in the study of this problem too.

Bio:

Noga Alon is a Professor of Mathematics at Princeton University and a Professor Emeritus of Mathematics and Computer Science at Tel Aviv University.

He works in Discrete Mathematics and its applications in Theoretical Computer Science, Information Theory, Combinatorial Geometry, and Combinatorial Number Theory.

He is a member of the Israel Academy of Sciences and Humanities and of the Academia Europaea, and an honorary member of the Hungarian Academy of Sciences. He received several awards, three recent ones are the 2022 Shaw Prize in Mathematical Sciences, the 2022 Knuth Prize for outstanding contributions to the foundations of computer science and the 2024 Wolf Prize in Mathematics.