License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.90
URN: urn:nbn:de:0030-drops-106665
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10666/
Go to the corresponding LIPIcs Volume Portal

Panagiotou, Konstantinos ; Pasch, Matija

Satisfiability Thresholds for Regular Occupation Problems

pdf-format:
LIPIcs-ICALP-2019-90.pdf (0.5 MB)

Abstract

In the last two decades the study of random instances of constraint satisfaction problems (CSPs) has flourished across several disciplines, including computer science, mathematics and physics. The diversity of the developed methods, on the rigorous and non-rigorous side, has led to major advances regarding both the theoretical as well as the applied viewpoints. The two most popular types of such CSPs are the Erdös-Rényi and the random regular CSPs.
Based on a ceteris paribus approach in terms of the density evolution equations known from statistical physics, we focus on a specific prominent class of problems of the latter type, the so-called occupation problems. The regular r-in-k occupation problems resemble a basis of this class. By now, out of these CSPs only the satisfiability threshold - the largest degree for which the problem admits asymptotically a solution - for the 1-in-k occupation problem has been rigorously established. In the present work we take a general approach towards a systematic analysis of occupation problems. In particular, we discover a surprising and explicit connection between the 2-in-k occupation problem satisfiability threshold and the determination of contraction coefficients, an important quantity in information theory measuring the loss of information that occurs when communicating through a noisy channel. We present methods to facilitate the computation of these coefficients and use them to establish explicitly the threshold for the 2-in-k occupation problem for k=4. Based on this result, for general k >= 5 we formulate a conjecture that pins down the exact value of the corresponding coefficient, which, if true, is shown to determine the threshold in all these cases.

BibTeX - Entry

@InProceedings{panagiotou_et_al:LIPIcs:2019:10666,
  author =	{Konstantinos Panagiotou and Matija Pasch},
  title =	{{Satisfiability Thresholds for Regular Occupation Problems}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{90:1--90:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10666},
  URN =		{urn:nbn:de:0030-drops-106665},
  doi =		{10.4230/LIPIcs.ICALP.2019.90},
  annote =	{Keywords: Constraint satisfaction problem, replica symmetric, contraction coefficient, first moment, second moment, small subgraph conditioning}
}

Keywords: Constraint satisfaction problem, replica symmetric, contraction coefficient, first moment, second moment, small subgraph conditioning
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI