TY - GEN
T1 - Unsatisfiability bounds for random CSPs from an energetic interpolation method
AU - Achlioptas, Dimitris
AU - Menchaca-Mendez, Ricardo
PY - 2012
Y1 - 2012
N2 - The interpolation method, originally developed in statistical physics, transforms distributions of random CSPs to distributions of much simpler problems while bounding the change in a number of associated statistical quantities along the transformation path. After a number of further mathematical developments, it is now known that, in principle, the method can yield rigorous unsatisfiability bounds if one "plugs in an appropriate functional distribution". A drawback of the method is that identifying appropriate distributions and plugging them in leads to major analytical challenges as the distributions required are, in fact, infinite dimensional objects. We develop a variant of the interpolation method for random CSPs on arbitrary sparse degree distributions which trades accuracy for tractability. In particular, our bounds only require the solution of a 1-dimensional optimization problem (which typically turns out to be very easy) and as such can be used to compute explicit rigorous unsatisfiability bounds.
AB - The interpolation method, originally developed in statistical physics, transforms distributions of random CSPs to distributions of much simpler problems while bounding the change in a number of associated statistical quantities along the transformation path. After a number of further mathematical developments, it is now known that, in principle, the method can yield rigorous unsatisfiability bounds if one "plugs in an appropriate functional distribution". A drawback of the method is that identifying appropriate distributions and plugging them in leads to major analytical challenges as the distributions required are, in fact, infinite dimensional objects. We develop a variant of the interpolation method for random CSPs on arbitrary sparse degree distributions which trades accuracy for tractability. In particular, our bounds only require the solution of a 1-dimensional optimization problem (which typically turns out to be very easy) and as such can be used to compute explicit rigorous unsatisfiability bounds.
UR - http://www.scopus.com/inward/record.url?scp=84883753464&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-31594-7_1
DO - 10.1007/978-3-642-31594-7_1
M3 - Contribución a la conferencia
SN - 9783642315930
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 12
BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
T2 - 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Y2 - 9 July 2012 through 13 July 2012
ER -