לוח שנה משולב

Vizing’s Theorem provides an algorithm that edge colors any graph of maximum degree Δ using Δ 1 colors, which is necessary for some graphs, and at most one higher than necessary for any graph. In online settings, the trivial greedy algorithm requires 2Δ-1 colors, and Bar-Noy, Motwani and Naor in the early 90s showed that this is best possible, at least in the low-degree regime. In contrast, they conjectured that for graphs of superlogarithmic-in-n maximum degree, much better can be done, and that even (1 o(1))Δ colors suffice online. This would make edge coloring a rare problem, for which "online is (nearly) as easy as offline". In this talk I will outline the history of this conjecture, and its recent resolution, together with extensions of a flavor resembling classic and recent results on *list* edge-coloring and “local” edge-coloring.

Talk based in part on joint works with many wonderful and colorful collaborators, including Sayan Bhattacharya, Joakim Blikstad, Ilan R. Cohen, Fabrizio Grandoni, Seffi Naor, Binghui Peng, Amin Saberi, Aravind Srinivasan, Ola Svensson and Radu Vintan.

Learning from data has led to paradigm shifts in a multitude of disciplines, including web, text and image search and generation, speech recognition, as well as bioinformatics. Can machine learning enable similar breakthroughs in understanding (quantum) molecules and materials? Aiming towards a unified machine learning (ML) model of molecular interactions in chemical space, I will discuss the potential and challenges for using ML techniques in chemistry and physics. ML methods can not only accurately estimate molecular properties of large datasets, but they can also lead to new insights into chemical similarity, aromaticity, reactivity, and molecular dynamics. For example, the combination of reliable molecular data with ML methods has enabled a fully quantitative simulation of protein dynamics in water (https://arxiv.org/abs/2205.08306). While the potential of machine learning for revealing insights into molecules and materials is high, I will conclude my talk by discussing the many remaining challenges.

TBA