| Título |
Unsatisfiability bounds for random CSPs from an energetic interpolation method |
| Tipo |
Congreso |
| Sub-tipo |
SCOPUS |
| Descripción |
Lecture Notes in Computer Science; 39th International Colloquium on Automata, Languages, and Programming |
| Resumen |
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. |
| Observaciones |
ICALP 2012; (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Code 99392 |
| Lugar |
Warwick |
| País |
Reino Unido |
| No. de páginas |
1-12 |
| Vol. / Cap. |
Vol. 7391 LNCS, Issue PART 1 |
| Inicio |
2012-07-09 |
| Fin |
2012-07-13 |
| ISBN/ISSN |
978-364231593-0 |
