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 nonrigorous 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ösRé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 socalled occupation problems. The regular rink 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 1ink 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 2ink 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 2ink 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:190:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10666},
URN = {urn:nbn:de:0030drops106665},
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 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) 
Issue Date: 

2019 
Date of publication: 

08.07.2019 