- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- The Local Cut Lemma
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
The Local Cut Lemma Bernshteyn, Anton
Description
The entropy compression method is an algorithmic technique that was invented by Moser and Tardos in order to give an effective proof of the Lovász 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 parts 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, it not only shows that a certain probability is positive, but also gives an explicit lower bound for that probability. In this talk, we will discuss the LCL and some of its applications, as well as its connections with the entropy compression.
Item Metadata
Title |
The Local Cut Lemma
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2016-10-18T10:47
|
Description |
The entropy compression method is an algorithmic technique that was invented by Moser and Tardos in order to give an effective proof of the Lovász 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 parts 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, it not only shows that a certain probability is positive, but also gives an explicit lower bound for that probability. In this talk, we will discuss the LCL and some of its applications, as well as its connections with the entropy compression.
|
Extent |
30 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: University of Illinois at Urbana-Champaign
|
Series | |
Date Available |
2017-04-19
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0343656
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International