research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleUnsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method
Bibtex cite IDRACTI-RU1-2012-18
Booktitle ICALP (1)
Year published 2012
Pages 1-12
Publisher Springer Berlin Heidelberg
Organization 39th International Colloquium, ICALP 2012, July 9-13, 2012, Proceedings, Part I
Location Warwick, UK
DOI 10.1007/978-3-642-31594-7_1
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.
Achlioptas, Dimitris
Menchaca-Mendez, Ricardo
CSPs.pdf (main file)
Publication ID966