The algorithmic Lovász local lemma provides an algorithmic way to construct objects that obey a system of constraints with limited dependence. It proves that, given a finite set of bad events and specific bounds on their respective probabilities, all of these events can be avoided with non-zero probability. Robin Moser and Gábor Tardos proposed a Las Vegas algorithm with expected polynomial runtime to compute an assignment to the random variables such that all events are avoided.
Stanford University
Fall 2022
This course dives into the use of randomness in algorithms and data structures, emphasizing the theoretical foundations of probabilistic analysis. Topics range from tail bounds, Markov chains, to randomized algorithms. The concepts are applied to machine learning, networking, and systems. Prerequisites indicate intermediate-level understanding required.
No concepts data
+ 37 more concepts