Formal Probabilistic Methods for Combinatorial Structures using the Lovász Local Lemma
Offered By: ACM SIGPLAN via YouTube
Course Description
Overview
Explore a 32-minute conference talk from CPP 2024 that delves into formalizing probabilistic methods for combinatorial structures using the Lovász Local Lemma. Learn how Chelsea Edmonds and Lawrence Paulson present a modular framework in Isabelle/HOL to translate intuitive probabilistic arguments into formal proofs. Discover the challenges and insights in formalizing the basic existence method and the first formalization of the Lovász local lemma. Gain understanding of general, reusable formal probabilistic lemmas for combinatorial structures and their application to classic lemmas on hypergraph colorings. Examine the gaps between intuitive probabilistic reasoning and formal proofs, and see how this work contributes to expanding formalized libraries of combinatorial mathematics using probability.
Syllabus
[CPP'24] Formal Probabilistic Methods for Combinatorial Structures using the Lovász Local ...
Taught by
ACM SIGPLAN
Related Courses
Introduction to High Dimensional Expanders - Irit DinurInstitute for Advanced Study via YouTube The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs
IEEE via YouTube Graph Representation Learning and Its Applications to Biomedicine
Applied Algebraic Topology Network via YouTube Asaf Shapira - Local vs Global Combinatorics
International Mathematical Union via YouTube Tropical Solutions to Hard Problems in Auction Theory and Neural Networks - Lecture II
Hausdorff Center for Mathematics via YouTube