The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Randomization is an important tool in algorithm design for obtaining efficient solutions; e.g., random pivot selection in quicksort lowers the expected runtime (ER) to O(n log n). Reasoning about the ER of randomized algorithms is subtle and full of nuances, as:
ER analysis of randomized algorithms is typically done using classical probability theory, mostly with arguments relying on random variable expectations or martingales. These analyses partially follow an ad-hoc reasoning and take non-trivial relationships between random variables for granted.
In this talk, I'll present a formal verification approach towards the ER analysis using a weakest-precondition approach à la Dijkstra. It allows e.g. to prove the positive almost-sure termination: does a program terminate with probability one in finite expected time? We show proof rules for loops prove the soundness w.r.t a simple operational mode and argue that our approach conservatively extends Nielson's approach for deterministic programs.