YoVDO

Formal Probabilistic Methods for Combinatorial Structures using the Lovász Local Lemma

Offered By: ACM SIGPLAN via YouTube

Tags

Probabilistic Methods Courses Combinatorics Courses Probability Theory Courses Formal Verification Courses Hypergraphs Courses

Course Description

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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

Probability for Computer Science
Indian Institute of Technology Kanpur via Swayam
Exploration with Limited Memory - Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits
Association for Computing Machinery (ACM) via YouTube
Probabilistic Methods for Increased Robustness in Machine Learning
Alan Turing Institute via YouTube
Stochastic Weighted Matching - 1-Epsilon Approximation
IEEE via YouTube
X-Ramanujan Graphs
Simons Institute via YouTube