IMDEA Software

Iniciativa IMDEA

Inicio > Eventos > Charlas Invitadas > 2026 > Refuting Equivalence in Probabilistic Programs with Conditioning
Esta página aún no ha sido traducida. A continuación se muestra la página en inglés.

Ehsan Kafshdar Goharshady

martes 14 de julio de 2026

11:00am 302-Mountain View and Zoom3 (https://zoom.us/j/3911012202, password:@s3)

Ehsan Kafshdar Goharshady, PhD Researcher, Institute of Science and Technology Austria)

Refuting Equivalence in Probabilistic Programs with Conditioning

Abstract:

We consider the problems of statically refuting equivalence and similarity of output distributions defined by a pair of probabilistic programs. Equivalence and similarity are two fundamental relational properties of probabilistic programs that are essential for their correctness both in implementation and in compilation. In this work, we present a new method for static equivalence and similarity refutation. Our method refutes equivalence and similarity by computing a function over program outputs whose expected value with respect to the output distributions of two programs is different. The function is computed simultaneously with an upper expectation supermartingale and a lower expectation submartingale for the two programs, which we show to together provide a sound and complete certificate for refuting equivalence and similarity.