## The Local Cut LemmaAdd to your list(s) Download to your calendar using vCal - Anton Bernshteyn (Illinois)
- Thursday 16 February 2017, 15:00-16:00
- LTC Watson.
If you have a question about this talk, please contact Dr Andrew Treglown. The entropy compression method is an algorithmic technique that was invented by Moser and Tardos in order to give an effective proof of the Lovasz Local Lemma (the LLL for short). It turns out that avoiding the LLL and applying the entropy compression method directly can lead to improvements, sometimes significant, in combinatorial bounds. The Local Cut Lemma (the LCL for short) is a generalization of the LLL that implies these new combinatorial results. It hides technical details of the method and thus makes the arguments simpler and shorter. Although the LCL was inspired by the entropy compression method, it has a direct probabilistic proof (similar to the classical proof of the LLL ); in particular, not only does the LCL show that a certain probability is positive, but it also provides an explicit lower bound for that probability. In this talk, I will present the LCL and explain how to use it. This talk is part of the Combinatorics and Probability Seminar series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsCond. Mat. seminar Postgraduate Seminars in the School of Computer Science What's on in Physics?## Other talksSubgroups of the Monster Multi-dimensional vector assignment problems (MVA) : Complexity, Approximation and Algorithms Isomorphic subgroups of finite solvable groups Characterization and propagation modeling in context aware environments RSC 2019 Dalton Emerging Researcher Award Lecture School Seminar |