A simple proof of the constructive Lovász Local Lemma and some extensions

Description of video

Date: 4/20/23
Speaker :Gilyén András


    I will describe an elementary proof of the constructive Lovász Local Lemma
    that could be understood at the level of an undergraduate course on discrete mathematics.
    The proof boils down to a plain counting argument and an inductive upper bound on
    the probabilities of certain events. The argument that I present is inspired by the
    "forward-looking" analysis of Harvey and Vondrák FOCS'15 (https://doi.org/10.1109/FOCS.2015.85)
    and is described in more details in a paper I wrote with Or Sattath FOCS'17 (https://doi.org/10.1109/FOCS.2017.47)
    If time permits I will mention some extensions related to "resampling oracles" and
    discuss the relevance to the constructive quantum Lovász Local Lemma.