Machine Checked Proofs and Programs in Algebraic Combinatorics
This program is tentative and subject to change.
We present a library of formalized results around symmetric functions and the character theory of the symmetric groups. Written in Coq/Rocq and based on the Mathematical component library, it covers a large part of the contents of a basic textbook in the field. The central result is a proof of the Littlewood-Richardson rule, which computes some integer numbers appearing in various fields of mathematics, and which has a long story of wrong proofs. A specific feature of algebraic combinatorics is the constant interplay between algorithms and algebraic constructions: algorithms are not only in computations, but also are key ingredients in definitions and proofs. As such, the proof of the Littlewood-Richardson rule deeply relies on the understanding of the execution of the Robinson-Schensted algorithm. Many results in this library are effective and actually used in computer algebra systems, and we discuss their certified implementation.
This program is tentative and subject to change.
Mon 20 JanDisplayed time zone: Mountain Time (US & Canada) change
11:00 - 12:30 | |||
11:00 30mTalk | Split Decisions: Explicit Contexts for Substructural Languagesdistinguished paper CPP Daniel Zackon McGill University, Chuta Sano McGill University, Alberto Momigliano Università degli Studi di Milano, Brigitte Pientka McGill University | ||
11:30 30mTalk | Machine Checked Proofs and Programs in Algebraic Combinatorics CPP Florent Hivert Univ. Paris-Saclay, LISN, LMF, CNRS, INRIA | ||
12:00 30mTalk | Monadic interpreters for concurrent memory models: Executable semantics of a concurrent subset of LLVM IRremote presentation CPP Nicolas Chappe Inria Lyon, LIP, Ludovic Henrio University of Lyon - ENS Lyon - UCBL - CNRS - Inria - LIP, Yannick Zakowski Inria |