Unsatisfiability bounds for random CSPs from an energetic interpolation method

Dimitris Achlioptas, Ricardo Menchaca-Mendez

Producción científica: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

1 Cita (Scopus)

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.

Idioma originalInglés
Título de la publicación alojadaAutomata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
Páginas1-12
Número de páginas12
EdiciónPART 1
DOI
EstadoPublicada - 2012
Publicado de forma externa
Evento39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, Reino Unido
Duración: 9 jul. 201213 jul. 2012

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NúmeroPART 1
Volumen7391 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
País/TerritorioReino Unido
CiudadWarwick
Período9/07/1213/07/12

Huella

Profundice en los temas de investigación de 'Unsatisfiability bounds for random CSPs from an energetic interpolation method'. En conjunto forman una huella única.

Citar esto