Symmetries in constraint satisfaction: Weisfeiler-Leman invariance and promise problems

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Butti, Silvia
• dc.contributor.other Dalmau, Víctor
• dc.contributor.other Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions
• dc.date.accessioned 2024-03-16T02:34:46Z
• dc.date.available 2024-03-16T02:34:46Z
• dc.date.issued 2022-10-26T12:15:34Z
• dc.date.issued 2022-10-26T12:15:34Z
• dc.date.issued 2022-10-20
• dc.date.modified 2024-03-15T10:58:05Z
• dc.description.abstract This thesis focuses on the complexity of the fixed-template Constraint Satisfaction Problem (CSP) and its variants. Our contributions are two-fold. On the one hand, we study how closure of the space of CSP instances under an equivalence relation induced by the 1-dimensional Weisfeiler-Leman algorithm correlates with solvability by the Sherali-Adams hierarchy of linear programs, invariance of the template under symmetric operations, and tractability by distributed algorithms. We then extend this analysis to the more general framework of Promise Valued CSPs. On the other hand, we initiate the study of the complexity of the Promise Model Checking Problem (PMC) parametrised by the model for the existential positive and the positive fragments of first-order logic. We lay the foundations for an algebraic approach to these problems, which allows us to fully characterize the complexity of the PMC for the existential positive fragment and to give a number of upper and lower bounds for the positive fragment.
• dc.description.abstract Esta tesis se centra en la complejidad del Problema de Satisfacción de Restricciones (Constraint Satisfaction Problem, CSP) de plantilla fija y sus variantes. Nuestras aportaciones se dividen en dos grupos. Por un lado, estudiamos cómo la clausura del espacio de instancias del CSP bajo una relación de equivalencia inducida por el algoritmo unidimensional de Weisfeiler-Leman se correlaciona con la resolubilidad por la jerarquía de programas lineales de Sherali-Adams, la invariabilidad de la plantilla bajo operaciones simétricas y la tratabilidad por algoritmos distribuidos. A continuación, extendemos esta análisis al marco más general de los Promise Valued CSPs. Por otro lado, iniciamos el estudio de la complejidad del Promise Model Checking Problem (PMC) parametrizado por el modelo para los fragmentos existencial positivo y positivo de la lógica de primer orden. Fijamos las bases de un enfoque algébrico para estos problemas, que nos permite caracterizar completamente la complejidad del PMC para el fragmento existencial positivo, y dar una serie de límites superiores e inferiores para el fragmento positivo.
• dc.description.abstract Aquesta tesi se centra en la complexitat del Problema de Satisfacció de Restriccions (Constraint Satisfaction Problem, CSP) de plantilla fixa i les seves variants. Les nostres aportacions es divideixen en dos grups. D'una banda, estudiem com la clausura de l'espai d'instàncies del CSP sota una relació d'equivalència induïda per l'algorisme unidimensional de Weisfeiler-Leman es correlaciona amb la resolubilitat per la jerarquia de programes lineals de Sherali-Adams, la invariabilitat de la plantilla sota operacions simètriques i la tractabilitat per algorismes distribuïts. A continuació, estenem aquesta anàlisi al marc més general dels Promise Valued CSPs. D'altra banda, iniciem l'estudi de la complexitat del Promise Model Checking Problem (PMC) parametritzat pel model per als fragments existencial positiu i positiu de la lògica de primer ordre. Fixem les bases d'un enfocament algèbric per aquests problemes, que ens permet caracteritzar completament la complexitat del PMC per al fragment existencial positiu i donar una sèrie de límits superiors i inferiors per al fragment positiu.
• dc.description.abstract Programa de doctorat en Tecnologies de la Informació i les Comunicacions
• dc.format 203 p.
• dc.format application/pdf
• dc.format application/pdf
• dc.identifier http://hdl.handle.net/10803/675788
• dc.identifier.uri http://hdl.handle.net/10230/54624
• dc.language.iso eng
• dc.publisher Universitat Pompeu Fabra
• dc.rights L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-sa/4.0/
• dc.rights http://creativecommons.org/licenses/by-nc-sa/4.0/
• dc.rights info:eu-repo/semantics/openAccess
• dc.source TDX (Tesis Doctorals en Xarxa)
• dc.subject.keyword Constraint satisfaction problems
• dc.subject.keyword Linear programming
• dc.subject.keyword Weisfeiler-Leman algorithm
• dc.subject.keyword Sherali-Adams hierarchy
• dc.subject.keyword Distributed algorithms
• dc.subject.keyword Model checking
• dc.subject.keyword Problema de satisfacción de restricciones
• dc.subject.keyword Programación lineal
• dc.subject.keyword Algoritmo de Weisfeiler-Leman
• dc.subject.keyword Jerarquía de Sherali-Adams
• dc.subject.keyword Algoritmos distribuidos
• dc.subject.keyword Verificación de modelos
• dc.subject.keyword Problema de satisfacció de restriccions
• dc.subject.keyword Programació lineal
• dc.subject.keyword Algoritme de Weisfeiler-Leman
• dc.subject.keyword Jerarquia de Sherali-Adams
• dc.subject.keyword Algorismes distribuïts
• dc.subject.keyword Verificació de models
• dc.subject.keyword 62
• dc.title Symmetries in constraint satisfaction: Weisfeiler-Leman invariance and promise problems
• dc.type info:eu-repo/semantics/doctoralThesis
• dc.type info:eu-repo/semantics/publishedVersion