Equivalence and Similarity Refutation for Probabilistic Programs

Explore a groundbreaking method for statically refuting equivalence and similarity of output distributions in probabilistic programs through this 18-minute video presentation from PLDI 2024. Delve into the innovative approach that combines upper expectation supermartingales and lower expectation submartingales to provide formal certificates for refutation. Learn how this fully automated technique applies to infinite-state probabilistic programs and offers formal guarantees on result correctness. Discover the method's effectiveness through experimental results on examples from literature. Gain insights into essential concepts such as probabilistic programming, static program analysis, probability distribution equivalence, Kantorovich distance, and martingales. Access supplementary materials, including reusable artifacts, to further explore this significant contribution to relational program analysis.

[PLDI24] Equivalence and Similarity Refutation for Probabilistic Programs