Colloquia and Seminars

Reinforcement learning policies in Markov decision processes (MDPs) often behave unexpectedly, especially in environments with sparse rewards, raising challenges for debugging and verification. We propose a general framework for discrete MDPs to generate two complementary, one-step explanations for single-action anomalies: (1) minimal counterfactual states—the smallest factored-state perturbations that flip a chosen action—and (2) robustness regions—contiguous state neighborhoods over which the original action remains invariant.

Without accessing internal model details, our black-box technique uses only action feedback, is applicable to any discrete RL setting, and has been validated on various Gymnasium environments, providing actionable understanding of when and why policies change their decisions.

We extend the Coupon Collector's Problem (CCP) and present a novel generalized model, referred as the \ekecd problem, where one is interested in recovering a bipartite graph with a perfect matching, which represents the coupons and their matching labels. We show two extra-extensions to this variation: the heterogeneous sample size case (\efmecd) and the partly recovering case.

The software landscape is showing consistent, accelerated growth in the volume of code developed using dynamic languages. These languages are characterized by dynamic typing and more lax preemptive checks, which allow rapid application development and shorter development cycles. The vast majority of these languages are interpreted; that is, programs are executed by an interpreter in a managed runtime environment. Such interpreters incur significant performance hits, and, to counter that, modern runtime environments usually employ some sort of optimization. The most common one is Just-in-Time compilation (JIT), which translates source code on-demand into native code that can run much faster. Some notable JIT engines (such as V8 for JavaScript) exhibit impressive speedups. Still, in most realistic scenarios, they cannot surpass the performance of hand-crafted native code written in a low-level language like C.

There are inherent reasons for why Ahead-of-Time compilation (AOT) is rarely practiced with dynamic languages. Since variables are dynamically typed, this will require most of the type-checking to be done at runtime still, thus limiting the range of optimization that can be performed ahead of time, consequently limiting the benefit of AOT compilation. We propose an approach that utilizes static analysis for the purpose of sound type inference, which can then be leveraged for code generation requiring minimal amount of runtime type checks. Unlike previous work in this area, our approach eliminates the need for the JIT at runtime, or, indeed, any managed runtime at all. We claim that real-world JavaScript applications can, in fact, benefit much from using AOT, in terms of increased speed. We show empirical evidence on a set of representative benchmarks supports this claim.

Min-Plus Weighted Finite Automata (WFAs) are a quantitative extension of Boolean automata whereby each word is assigned an integer, instead of being accepted or rejected.

Applications of WFAs fall on a wide spectrum including verification, rewriting systems, tropical algebra, speech and image processing and have been key to proving the star-height conjecture. 
Unlike Boolean automata, WFAs cannot always be determinized. The decidability of whether a WFA admits an equivalent deterministic WFA is a long standing open problem.

We prove that this problem is decidable.
As part of the proof, we develop a new toolbox for reasoning about the run structure of weighted automata.

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.