A simple algorithmic proof of the symmetric lopsided Lovász local lemma

Lefteris Kirousis; John Livieratos

doi:10.1007/978-3-030-05348-2_5

A simple algorithmic proof of the symmetric lopsided Lovász local lemma

Lefteris Kirousis, John Livieratos

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We provide a simple algorithmic proof for the symmetric Lopsided Lovász Local Lemma, a variant of the classic Lovász Local Lemma, where, roughly, only the degree of the negatively correlated undesirable events counts. Our analysis refers to the algorithm by Moser (2009), however it is based on a simple application of the probabilistic method, rather than a counting argument, as are most of the analyses of algorithms for variants of the Lovász Local Lemma.

Original language	English (US)
Title of host publication	Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers
Editors	Panos M. Pardalos, Roberto Battiti, Mauro Brunato, Ilias Kotsireas
Publisher	Springer Verlag
Pages	49-63
Number of pages	15
ISBN (Print)	9783030053475
DOIs	https://doi.org/10.1007/978-3-030-05348-2_5
State	Published - 2019
Event	12th International Conference on Learning and Intelligent Optimization, LION 12 - Kalamata, Greece Duration: Jun 10 2018 → Jun 15 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11353 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Conference on Learning and Intelligent Optimization, LION 12
Country/Territory	Greece
City	Kalamata
Period	6/10/18 → 6/15/18

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-05348-2_5

Cite this

Kirousis, L., & Livieratos, J. (2019). A simple algorithmic proof of the symmetric lopsided Lovász local lemma. In P. M. Pardalos, R. Battiti, M. Brunato, & I. Kotsireas (Eds.), Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers (pp. 49-63). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11353 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-05348-2_5

A simple algorithmic proof of the symmetric lopsided Lovász local lemma. / Kirousis, Lefteris; Livieratos, John.
Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers. ed. / Panos M. Pardalos; Roberto Battiti; Mauro Brunato; Ilias Kotsireas. Springer Verlag, 2019. p. 49-63 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11353 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kirousis, L & Livieratos, J 2019, A simple algorithmic proof of the symmetric lopsided Lovász local lemma. in PM Pardalos, R Battiti, M Brunato & I Kotsireas (eds), Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11353 LNCS, Springer Verlag, pp. 49-63, 12th International Conference on Learning and Intelligent Optimization, LION 12, Kalamata, Greece, 6/10/18. https://doi.org/10.1007/978-3-030-05348-2_5

Kirousis L, Livieratos J. A simple algorithmic proof of the symmetric lopsided Lovász local lemma. In Pardalos PM, Battiti R, Brunato M, Kotsireas I, editors, Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers. Springer Verlag. 2019. p. 49-63. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-05348-2_5

Kirousis, Lefteris ; Livieratos, John. / A simple algorithmic proof of the symmetric lopsided Lovász local lemma. Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers. editor / Panos M. Pardalos ; Roberto Battiti ; Mauro Brunato ; Ilias Kotsireas. Springer Verlag, 2019. pp. 49-63 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{46f3e1fb826c4d33ae0e1b5f9fd0d93d,

title = "A simple algorithmic proof of the symmetric lopsided Lov{\'a}sz local lemma",

abstract = "We provide a simple algorithmic proof for the symmetric Lopsided Lov{\'a}sz Local Lemma, a variant of the classic Lov{\'a}sz Local Lemma, where, roughly, only the degree of the negatively correlated undesirable events counts. Our analysis refers to the algorithm by Moser (2009), however it is based on a simple application of the probabilistic method, rather than a counting argument, as are most of the analyses of algorithms for variants of the Lov{\'a}sz Local Lemma.",

author = "Lefteris Kirousis and John Livieratos",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 12th International Conference on Learning and Intelligent Optimization, LION 12 ; Conference date: 10-06-2018 Through 15-06-2018",

year = "2019",

doi = "10.1007/978-3-030-05348-2_5",

language = "English (US)",

isbn = "9783030053475",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "49--63",

editor = "Pardalos, {Panos M.} and Roberto Battiti and Mauro Brunato and Ilias Kotsireas",

booktitle = "Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers",

}

TY - GEN

T1 - A simple algorithmic proof of the symmetric lopsided Lovász local lemma

AU - Kirousis, Lefteris

AU - Livieratos, John

PY - 2019

Y1 - 2019

N2 - We provide a simple algorithmic proof for the symmetric Lopsided Lovász Local Lemma, a variant of the classic Lovász Local Lemma, where, roughly, only the degree of the negatively correlated undesirable events counts. Our analysis refers to the algorithm by Moser (2009), however it is based on a simple application of the probabilistic method, rather than a counting argument, as are most of the analyses of algorithms for variants of the Lovász Local Lemma.

AB - We provide a simple algorithmic proof for the symmetric Lopsided Lovász Local Lemma, a variant of the classic Lovász Local Lemma, where, roughly, only the degree of the negatively correlated undesirable events counts. Our analysis refers to the algorithm by Moser (2009), however it is based on a simple application of the probabilistic method, rather than a counting argument, as are most of the analyses of algorithms for variants of the Lovász Local Lemma.

UR - http://www.scopus.com/inward/record.url?scp=85059933813&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059933813&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-05348-2_5

DO - 10.1007/978-3-030-05348-2_5

M3 - Conference contribution

AN - SCOPUS:85059933813

SN - 9783030053475

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 49

EP - 63

BT - Learning and Intelligent Optimization - 12th International Conference, LION 12, Revised Selected Papers

A2 - Pardalos, Panos M.

A2 - Battiti, Roberto

A2 - Brunato, Mauro

A2 - Kotsireas, Ilias

PB - Springer Verlag

T2 - 12th International Conference on Learning and Intelligent Optimization, LION 12

Y2 - 10 June 2018 through 15 June 2018

ER -

A simple algorithmic proof of the symmetric lopsided Lovász local lemma

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this