Search Results

Documents authored by Achlioptas, Dimitris

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.8
Local Approximations of the Independent Set Polynomial

Authors: Dimitris Achlioptas and Kostas Zampetakis

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The independent set polynomial of a graph has one variable for each vertex and one monomial for each independent set, comprising the product of the corresponding variables. Given a graph G on n vertices and a vector p ∈ [0,1)ⁿ, a central problem in statistical mechanics is determining whether the independent set polynomial of G is non-vanishing in the polydisk of p, i.e., whether |Z_G(x)| > 0 for every x ∈ ℂⁿ such that |x_i| ≤ p_i. Remarkably, when this holds, Z_G(-p) is a lower bound for the avoidance probability when G is a dependency graph for n events whose probabilities form vector p. A local sufficient condition for |Z_G| > 0 in the polydisk of p is the Lovász Local Lemma (LLL). In this work we derive several new results on the efficient evaluation and bounding of Z_G. Our starting point is a monotone mapping from subgraphs of G to truncations of the tree of self-avoiding walks of G. Using this mapping our first result is a local upper bound for Z(-p), similar in spirit to the local lower bound for Z(-p) provided by the LLL. Next, using this mapping, we show that when G is chordal, Z_G can be computed exactly and in linear time on the entire complex plane, implying perfect sampling for the hard-core model on chordal graphs. We also revisit the task of bounding Z(-p) from below, i.e., the LLL setting, and derive four new lower bounds of increasing sophistication. Already our simplest (and weakest) bound yields a strict improvement of the famous asymmetric LLL, i.e., a strict relaxation of the inequalities of the asymmetric LLL without any further assumptions. This new asymmetric local lemma is sharp enough to recover Shearer’s optimal bound in terms of the maximum degree Δ(G). We also apply our more sophisticated bounds to estimate the zero-free region of the hard-core model on the triangular lattice (hard hexagons model).
Cite as

Dimitris Achlioptas and Kostas Zampetakis. Local Approximations of the Independent Set Polynomial. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{achlioptas_et_al:LIPIcs.ICALP.2021.8,
  author =	{Achlioptas, Dimitris and Zampetakis, Kostas},
  title =	{{Local Approximations of the Independent Set Polynomial}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.8},
  URN =		{urn:nbn:de:0030-drops-140773},
  doi =		{10.4230/LIPIcs.ICALP.2021.8},
  annote =	{Keywords: Independent Set Polynomial, Lov\'{a}sz Local Lemma, Self-avoiding Walks}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019
LIPIcs, Volume 145, APPROX/RANDOM'19, Complete Volume

Authors: Dimitris Achlioptas and László A. Végh

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
LIPIcs, Volume 145, APPROX/RANDOM'19, Complete Volume
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{achlioptas_et_al:LIPIcs.APPROX-RANDOM.2019,
  title =	{{LIPIcs, Volume 145, APPROX/RANDOM'19, Complete Volume}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019},
  URN =		{urn:nbn:de:0030-drops-113014},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019},
  annote =	{Keywords: Mathematics of computing; Theory of computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Dimitris Achlioptas and László A. Végh

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 0:i-0:xxii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{achlioptas_et_al:LIPIcs.APPROX-RANDOM.2019.0,
  author =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{0:i--0:xxii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.0},
  URN =		{urn:nbn:de:0030-drops-112155},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.83
Stochastic Control via Entropy Compression

Authors: Dimitris Achlioptas, Fotis Iliopoulos, and Nikos Vlassis

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Consider an agent trying to bring a system to an acceptable state by repeated probabilistic action. Several recent works on algorithmizations of the Lovász Local Lemma (LLL) can be seen as establishing sufficient conditions for the agent to succeed. Here we study whether such stochastic control is also possible in a noisy environment, where both the process of state-observation and the process of state-evolution are subject to adversarial perturbation (noise). The introduction of noise causes the tools developed for LLL algorithmization to break down since the key LLL ingredient, the sparsity of the causality (dependence) relationship, no longer holds. To overcome this challenge we develop a new analysis where entropy plays a central role, both to measure the rate at which progress towards an acceptable state is made and the rate at which noise undoes this progress. The end result is a sufficient condition that allows a smooth tradeoff between the intensity of the noise and the amenability of the system, recovering an asymmetric LLL condition in the noiseless case.
Cite as

Dimitris Achlioptas, Fotis Iliopoulos, and Nikos Vlassis. Stochastic Control via Entropy Compression. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 83:1-83:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{achlioptas_et_al:LIPIcs.ICALP.2017.83,
  author =	{Achlioptas, Dimitris and Iliopoulos, Fotis and Vlassis, Nikos},
  title =	{{Stochastic Control via Entropy Compression}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{83:1--83:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.83},
  URN =		{urn:nbn:de:0030-drops-74279},
  doi =		{10.4230/LIPIcs.ICALP.2017.83},
  annote =	{Keywords: Stochastic Control, Lovasz Local Lemma}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.16
Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion

Authors: Dimitris Achlioptas and Themis Gouleakis

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
The Lovasz Local Lemma (LLL) is a powerful tool that can be used to prove that an object having none of a set of bad properties exists, using the probabilistic method. In many applications of the LLL it is also desirable to explicitly construct the combinatorial object. Recently it was shown that this is possible using a randomized algorithm in the full asymmetric LLL setting [R. Moser and G. Tardos, 2010]. A strengthening of the LLL for the case of dense local neighborhoods proved in [R. Bissacot et al., 2010] was recently also made constructive in [W. Pegden, 2011]. In another recent work [B. Haupler, B. Saha, A. Srinivasan, 2010], it was proved that the algorithm of Moser and Tardos is still efficient even when the number of events is exponential. Here we prove that these last two contributions can be combined to yield a new version of the LLL.
Cite as

Dimitris Achlioptas and Themis Gouleakis. Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 16-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{achlioptas_et_al:LIPIcs.FSTTCS.2012.16,
  author =	{Achlioptas, Dimitris and Gouleakis, Themis},
  title =	{{Algorithmic Improvements of the Lov\'{a}sz Local Lemma via Cluster Expansion}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{16--23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.16},
  URN =		{urn:nbn:de:0030-drops-38440},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.16},
  annote =	{Keywords: Probabilistic Method, Lov\'{a}sz Local Lemma, Algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact