Skip to main content

SISTEMAS DE PRUEBA MAS ALLA DE RESOLUCION: ANALISIS TEORICO

PID2019-109137GB-C22

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Call Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Call year 2019
State Plan 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSITAT POMPEU FABRA CCT

Resultados relacionados

Resultados totales (Incluyendo duplicados): 18
Encontrada(s) 1 página(s)

Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

Promise constraint satisfaction and width

  • Atserias, Albert
  • Dalmau, Víctor
Comunicació presentada a 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), celebrat del 9 al 12 de gener de 2022 de manera virtual., We study the power of the bounded-width consistency algorithm in the context of the fixed-template Promise Constraint Satisfaction Problem (PCSP). Our main technical finding is that the template of every PCSP that is solvable in bounded width satisfies a certain structural condition implying that its algebraic closure-properties include weak near unanimity polymorphisms of all large arities. While this parallels the standard (non-promise) CSP theory, the method of proof is quite different and applies even to the regime of sublinear width. We also show that, in contrast with the CSP world, the presence of weak near unanimity polymorphisms of all large arities does not guarantee solvability in bounded width. The separating example is even solvable in the second level of the Sherali-Adams (SA) hierarchy of linear programming relaxations. This shows that, unlike for CSPs, linear programming can be stronger than bounded width. A direct application of these methods also show that the problem of q-coloring p-colorable graphs is not solvable in bounded or even sublinear width, for any two constants p and q such that 3 ≤ p ≤ q. Turning to algorithms, we note that Wigderson's algorithm for O( √ n)-coloring 3-colorable graphs with n vertices is implementable in width 4. Indeed, by generalizing the method we see that, for any ∊ > 0 smaller than 1/2, the optimal width for solving the problem of O(n∊)-coloring 3-colorable graphs with n vertices lies between n1–3∊ and n1–2∊. The upper bound gives a simple exp(Θ(n1–2∊ log(n)))-time algorithm that, asymptotically, beats the straightforward exp(Θ(n1–∊)) bound that follows from partitioning the graph into O(n∊) many independent parts each of size O(n1–∊)., Albert Atserias: Partially funded by the MICIN through grant PID2019-109137GB-C22 (PROOFS) and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M). Víctor Dalmau: Partially funded by the MICIN through grant PID2019-109137GB-C22 (PROOFS).
Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the constraint satisfaction problem

  • Butti, Silvia
  • Dalmau, Víctor
Comunicació presentada a: MFCS 2021 celebrat del 23 a 27 d'agost de 2021 a Tallinn, Estònia., Given a pair of graphs 𝐀 and 𝐁, the problems of deciding whether there exists either a homomorphism or an isomorphism from 𝐀 to 𝐁 have received a lot of attention. While graph homomorphism is known to be NP-complete, the complexity of the graph isomorphism problem is not fully understood. A well-known combinatorial heuristic for graph isomorphism is the Weisfeiler-Leman test together with its higher order variants. On the other hand, both problems can be reformulated as integer programs and various LP methods can be applied to obtain high-quality relaxations that can still be solved efficiently. We study so-called fractional relaxations of these programs in the more general context where 𝐀 and 𝐁 are not graphs but arbitrary relational structures. We give a combinatorial characterization of the Sherali-Adams hierarchy applied to the homomorphism problem in terms of fractional isomorphism. Collaterally, we also extend a number of known results from graph theory to give a characterization of the notion of fractional isomorphism for relational structures in terms of the Weisfeiler-Leman test, equitable partitions, and counting homomorphisms from trees. As a result, we obtain a description of the families of CSPs that are closed under Weisfeiler-Leman invariance in terms of their polymorphisms as well as decidability by the first level of the Sherali-Adams hierarchy., Silvia Butti: The project that gave rise to these results received the support of a fellowship from “la Caixa” Foundation (ID 100010434). The fellowship code is LCF/BQ/DI18/11660056. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 713673. Víctor Dalmau: Víctor Dalmau was supported by MICCIN grant PID2019-109137GB-C22.
Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

The complexity of the distributed constraint satisfaction problem

  • Butti, Silvia
  • Dalmau, Víctor
Comunicació presentada a: STACS 2021 celebrat del 16 a 19 de març de 2021 a Saarbrücken, Alemanya., We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with each other by sending messages through fixed communication channels. Our results endorse the well-known fact from classical CSPs that the complexity of fixed-template computational problems depends on the template’s invariance under certain operations. Specifically, we show that DCSP(Γ) is polynomial-time tractable if and only if Γ is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP(Γ) in finite time. We also show that the same condition holds for the search variant of DCSP. Collaterally, our results unveil a feature of the processes’ neighbourhood in a distributed network, its iterated degree, which plays a major role in the analysis. We explore this notion establishing a tight connection with the basic linear programming relaxation of a CSP., The project that gave rise to these results received the support of a fellowship from “la Caixa” Foundation (ID 100010434). The fellowship code is LCF/BQ/DI18/11660056. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No. 713673. Victor Dalmau was supported by MICCIN grants TIN2016-76573-C2-1P and PID2019-109137GB-C22.
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

  • Bonacina, Ilario|||0000-0002-5697-8070
  • Galesi, Nicola
  • Lauria, Massimo
Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size., The first author was supported by the MICIN grants PID2019-109137GB-C22 and IJC2018-035334-I, and partially by the grant PID2019-109137GB-C21., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

On the consistency of circuit lower bounds for non-deterministic time

  • Atserias, Albert|||0000-0002-3732-1989
  • Buss, Sam
  • Müller, Moritz
We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory ‍V20 is consistent with the conjecture that ‍NEXP ‍⊈ ‍P/poly, i.e., some problem that is solvable in non-deterministic exponential time does not have polynomial size circuits. We suggest this is the best currently available evidence for the truth of the conjecture. Additionally, we establish a magnification result on the hardness of proving circuit lower bounds., Albert Atserias: Supported in part by Project PID2019-109137GB-C22 (PROOFS) and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M) of the Spanish State Research Agency. Sam Buss: Supported in part by Simons Foundation grant 578919., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

On the expressive power of homomorphism counts

  • Atserias, Albert|||0000-0002-3732-1989
  • Kolaitis, Phokion
  • Wu, Wei-Lin
A classical result by Lovász asserts that two graphs G and H are isomorphic if and only if they have the same left profile, that is, for every graph F, the number of homomorphisms from F to G coincides with the number of homomorphisms from F to H. Dvorák and later on Dell, Grohe, and Rattan showed that restrictions of the left profile to a class of graphs can capture several different relaxations of isomorphism, including equivalence in counting logics with a fixed number of variables (which contains fractional isomorphism as a special case) and co-spectrality (i.e., two graphs having the same characteristic polynomial). On the other side, a result by Chaudhuri and Vardi asserts that isomorphism is also captured by the right profile, that is, two graphs G and H are isomorphic if and only if for every graph F, the number of homomorphisms from G to F coincides with the number of homomorphisms from H to F. In this paper, we embark on a study of the restrictions of the right profile by investigating relaxations of isomorphism that can or cannot be captured by restricting the right profile to a fixed class of graphs. Our results unveil striking differences between the expressive power of the left profile and the right profile. We show that fractional isomorphism, equivalence in counting logics with a fixed number of variables, and co-spectrality cannot be captured by restricting the right profile to a class of graphs. In the opposite direction, we show that chromatic equivalence cannot be captured by restricting the left profile to a class of graphs, while, clearly, it can be captured by restricting the right profile to the class of all cliques., The research of Albert Atserias was partially supported by MICIN project PID2019-109137GBC22 (PROOFS). The research of Phokion Kolaitis and Wei-Lin Wu was partially supported by NSF Grant 1814152., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Polynomial calculus for MaxSAT

  • Bonacina, Ilario|||0000-0002-5697-8070
  • Bonet Carbonell, M. Luisa|||0000-0003-1646-7177
  • Levy Díaz, Jordi
MaxSAT is the problem of finding an assignment satisfying the maximum number of clauses in a CNF formula. We consider a natural generalization of this problem to generic sets of polynomials and propose a weighted version of Polynomial Calculus to address this problem. Weighted Polynomial Calculus is a natural generalization of MaxSAT-Resolution and weighted Resolution that manipulates polynomials with coefficients in a finite field and either weights in N or Z. We show the soundness and completeness of these systems via an algorithmic procedure. Weighted Polynomial Calculus, with weights in N and coefficients in F2, is able to prove efficiently that Tseitin formulas on a connected graph are minimally unsatisfiable. Using weights in Z, it also proves efficiently that the Pigeonhole Principle is minimally unsatisfiable., This work was supported by the Spanish Agencia Estatal de Investigación with the grant PID2019-109137GB-C21/AEI/10.13039/501100011033 and the grant PID2019-109137GBC22/AEI/10.13039/501100011033. Ilario Bonacina: Partially supported by the grant IJC2018-035334-I/AEI/10.13039/501100011033. Maria Luisa Bonet: Partially supported by Simons Institute. Jordi Levy: Partially supported by Simons Institute., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

The linear arrangement library: A new tool for research on syntactic dependency structures

  • Alemany Puig, Lluís|||0000-0002-3874-991X
  • Esteban Ángeles, Juan Luis|||0000-0003-0072-6576
  • Ferrer Cancho, Ramon|||0000-0002-7820-923X
The new and growing field of Quantitative Dependency Syntax has emerged at the crossroads between Dependency Syntax and Quantitative Linguistics. One of the main concerns in this field is the statistical patterns of syntactic dependency structures. These structures, grouped in treebanks, are the source for statistical analyses in these and related areas; dozens of scores devised over the years are the tools of a new industry to search for patterns and perform other sorts of analyses. The plethora of such metrics and their increasing complexity require sharing the source code of the programs used to perform such analyses. However, such code is not often shared with the scientific community or is tested following unknown standards. Here we present a new open-source tool, the Linear Arrangement Library (LAL), which caters to the needs of, especially, inexperienced programmers. This tool enables the calculation of these metrics on single syntactic dependency structures, treebanks, and collection of treebanks, grounded on ease of use and yet with great flexibility. LAL has been designed to be efficient, easy to use (while satisfying the needs of all levels of programming expertise), reliable (thanks to thorough testing), and to unite research from different traditions, geographic areas, and research fields., LAP is supported by Secretaria d’Universitats i Recerca de la Generalitat de Catalunya and the Social European Fund. RFC and LAP are supported by the grant TIN2017-89244-R from MINECO (Ministerio de Economía, Industria y Competitividad). RFC is also supported by the recognition 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya). JLE is funded by the grant PID2019-109137GB-C22 from MINECO., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Structure and complexity of bag consistency

  • Atserias, Albert|||0000-0002-3732-1989
  • Kolaitis, Phokion
Since the early days of relational databases, it was realized that acyclic hypergraphs give rise to database schemas with desirable structural and algorithmic properties. In a by-now classical paper, Beeri, Fagin, Maier, and Yannakakis established several different equivalent characterizations of acyclicity; in particular, they showed that the sets of attributes of a schema form an acyclic hypergraph if and only if the local-to-global consistency property for relations over that schema holds, which means that every collection of pairwise consistent relations over the schema is globally consistent. Even though real-life databases consist of bags (multisets), there has not been a study of the interplay between local consistency and global consistency for bags. We embark on such a study here and we first show that the sets of attributes of a schema form an acyclic hypergraph if and only if the local-to-global consistency property for bags over that schema holds. After this, we explore algorithmic aspects of global consistency for bags by analyzing the computational complexity of the global consistency problem for bags: given a collection of bags, are these bags globally consistent? We show that this problem is in NP, even when the schema is part of the input. We then establish the following dichotomy theorem for fixed schemas: if the schema is acyclic, then the global consistency problem for bags is solvable in polynomial time, while if the schema is cyclic, then the global consistency problem for bags is NP-complete. The latter result contrasts sharply with the state of affairs for relations, where, for each fixed schema, the global consistency problem for relations is solvable in polynomial time., The research of Albert Atserias was partially supported by MICIN project PID2019-109137GB-C22 (PROOFS). The research of Phokion Kolaitis was partially supported by NSF Award No. 1814152., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the constraint satisfaction problem

  • Butti, Silvia
  • Dalmau, Víctor
Comunicació presentada a: MFCS 2021 celebrat del 23 a 27 d'agost de 2021 a Tallinn, Estònia., Given a pair of graphs 𝐀 and 𝐁, the problems of deciding whether there exists either a homomorphism or an isomorphism from 𝐀 to 𝐁 have received a lot of attention. While graph homomorphism is known to be NP-complete, the complexity of the graph isomorphism problem is not fully understood. A well-known combinatorial heuristic for graph isomorphism is the Weisfeiler-Leman test together with its higher order variants. On the other hand, both problems can be reformulated as integer programs and various LP methods can be applied to obtain high-quality relaxations that can still be solved efficiently. We study so-called fractional relaxations of these programs in the more general context where 𝐀 and 𝐁 are not graphs but arbitrary relational structures. We give a combinatorial characterization of the Sherali-Adams hierarchy applied to the homomorphism problem in terms of fractional isomorphism. Collaterally, we also extend a number of known results from graph theory to give a characterization of the notion of fractional isomorphism for relational structures in terms of the Weisfeiler-Leman test, equitable partitions, and counting homomorphisms from trees. As a result, we obtain a description of the families of CSPs that are closed under Weisfeiler-Leman invariance in terms of their polymorphisms as well as decidability by the first level of the Sherali-Adams hierarchy., Silvia Butti: The project that gave rise to these results received the support of a fellowship from “la Caixa” Foundation (ID 100010434). The fellowship code is LCF/BQ/DI18/11660056. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 713673. Víctor Dalmau: Víctor Dalmau was supported by MICCIN grant PID2019-109137GB-C22.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Structure and complexity of bag consistency

  • Atserias, Albert
  • Kolaitis, Phokion
Since the early days of relational databases, it was realized that acyclic hypergraphs give rise to database schemas with desirable structural and algorithmic properties. In a by-now classical paper, Beeri, Fagin, Maier, and Yannakakis established several different equivalent characterizations of acyclicity; in particular, they showed that the sets of attributes of a schema form an acyclic hypergraph if and only if the local-to-global consistency property for relations over that schema holds, which means that every collection of pairwise consistent relations over the schema is globally consistent. Even though real-life databases consist of bags (multisets), there has not been a study of the interplay between local consistency and global consistency for bags. We embark on such a study here and we first show that the sets of attributes of a schema form an acyclic hypergraph if and only if the local-to-global consistency property for bags over that schema holds. After this, we explore algorithmic aspects of global consistency for bags by analyzing the computational complexity of the global consistency problem for bags: given a collection of bags, are these bags globally consistent? We show that this problem is in NP, even when the schema is part of the input. We then establish the following dichotomy theorem for fixed schemas: if the schema is acyclic, then the global consistency problem for bags is solvable in polynomial time, while if the schema is cyclic, then the global consistency problem for bags is NP-complete. The latter result contrasts sharply with the state of affairs for relations, where, for each fixed schema, the global consistency problem for relations is solvable in polynomial time., The research of Albert Atserias was partially supported by MICIN project PID2019-109137GB-C22 (PROOFS). The research of Phokion Kolaitis was partially supported by NSF Award No. 1814152., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Polynomial calculus for MaxSAT

  • Bonacina, Ilario
  • Bonet Carbonell, M. Luisa
  • Levy Díaz, Jordi
MaxSAT is the problem of finding an assignment satisfying the maximum number of clauses in a CNF formula. We consider a natural generalization of this problem to generic sets of polynomials and propose a weighted version of Polynomial Calculus to address this problem. Weighted Polynomial Calculus is a natural generalization of MaxSAT-Resolution and weighted Resolution that manipulates polynomials with coefficients in a finite field and either weights in N or Z. We show the soundness and completeness of these systems via an algorithmic procedure. Weighted Polynomial Calculus, with weights in N and coefficients in F2, is able to prove efficiently that Tseitin formulas on a connected graph are minimally unsatisfiable. Using weights in Z, it also proves efficiently that the Pigeonhole Principle is minimally unsatisfiable., This work was supported by the Spanish Agencia Estatal de Investigación with the grant PID2019-109137GB-C21/AEI/10.13039/501100011033 and the grant PID2019-109137GBC22/AEI/10.13039/501100011033. Ilario Bonacina: Partially supported by the grant IJC2018-035334-I/AEI/10.13039/501100011033. Maria Luisa Bonet: Partially supported by Simons Institute. Jordi Levy: Partially supported by Simons Institute., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

On the expressive power of homomorphism counts

  • Atserias, Albert
  • Kolaitis, Phokion
  • Wu, Wei-Lin
A classical result by Lovász asserts that two graphs G and H are isomorphic if and only if they have the same left profile, that is, for every graph F, the number of homomorphisms from F to G coincides with the number of homomorphisms from F to H. Dvorák and later on Dell, Grohe, and Rattan showed that restrictions of the left profile to a class of graphs can capture several different relaxations of isomorphism, including equivalence in counting logics with a fixed number of variables (which contains fractional isomorphism as a special case) and co-spectrality (i.e., two graphs having the same characteristic polynomial). On the other side, a result by Chaudhuri and Vardi asserts that isomorphism is also captured by the right profile, that is, two graphs G and H are isomorphic if and only if for every graph F, the number of homomorphisms from G to F coincides with the number of homomorphisms from H to F. In this paper, we embark on a study of the restrictions of the right profile by investigating relaxations of isomorphism that can or cannot be captured by restricting the right profile to a fixed class of graphs. Our results unveil striking differences between the expressive power of the left profile and the right profile. We show that fractional isomorphism, equivalence in counting logics with a fixed number of variables, and co-spectrality cannot be captured by restricting the right profile to a class of graphs. In the opposite direction, we show that chromatic equivalence cannot be captured by restricting the left profile to a class of graphs, while, clearly, it can be captured by restricting the right profile to the class of all cliques., The research of Albert Atserias was partially supported by MICIN project PID2019-109137GBC22 (PROOFS). The research of Phokion Kolaitis and Wei-Lin Wu was partially supported by NSF Grant 1814152., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

The linear arrangement library: A new tool for research on syntactic dependency structures

  • Alemany Puig, Lluís
  • Esteban Ángeles, Juan Luis
  • Ferrer Cancho, Ramon
The new and growing field of Quantitative Dependency Syntax has emerged at the crossroads between Dependency Syntax and Quantitative Linguistics. One of the main concerns in this field is the statistical patterns of syntactic dependency structures. These structures, grouped in treebanks, are the source for statistical analyses in these and related areas; dozens of scores devised over the years are the tools of a new industry to search for patterns and perform other sorts of analyses. The plethora of such metrics and their increasing complexity require sharing the source code of the programs used to perform such analyses. However, such code is not often shared with the scientific community or is tested following unknown standards. Here we present a new open-source tool, the Linear Arrangement Library (LAL), which caters to the needs of, especially, inexperienced programmers. This tool enables the calculation of these metrics on single syntactic dependency structures, treebanks, and collection of treebanks, grounded on ease of use and yet with great flexibility. LAL has been designed to be efficient, easy to use (while satisfying the needs of all levels of programming expertise), reliable (thanks to thorough testing), and to unite research from different traditions, geographic areas, and research fields., LAP is supported by Secretaria d’Universitats i Recerca de la Generalitat de Catalunya and the Social European Fund. RFC and LAP are supported by the grant TIN2017-89244-R from MINECO (Ministerio de Economía, Industria y Competitividad). RFC is also supported by the recognition 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya). JLE is funded by the grant PID2019-109137GB-C22 from MINECO., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

On the consistency of circuit lower bounds for non-deterministic time

  • Atserias, Albert
  • Buss, Sam
  • Müller, Moritz
We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory ‍V20 is consistent with the conjecture that ‍NEXP ‍⊈ ‍P/poly, i.e., some problem that is solvable in non-deterministic exponential time does not have polynomial size circuits. We suggest this is the best currently available evidence for the truth of the conjecture. Additionally, we establish a magnification result on the hardness of proving circuit lower bounds., Albert Atserias: Supported in part by Project PID2019-109137GB-C22 (PROOFS) and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M) of the Spanish State Research Agency. Sam Buss: Supported in part by Simons Foundation grant 578919., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

  • Bonacina, Ilario
  • Galesi, Nicola
  • Lauria, Massimo
Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size., The first author was supported by the MICIN grants PID2019-109137GB-C22 and IJC2018-035334-I, and partially by the grant PID2019-109137GB-C21., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

The complexity of the distributed constraint satisfaction problem

  • Butti, Silvia
  • Dalmau, Víctor
Comunicació presentada a: STACS 2021 celebrat del 16 a 19 de març de 2021 a Saarbrücken, Alemanya., We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with each other by sending messages through fixed communication channels. Our results endorse the well-known fact from classical CSPs that the complexity of fixed-template computational problems depends on the template’s invariance under certain operations. Specifically, we show that DCSP(Γ) is polynomial-time tractable if and only if Γ is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP(Γ) in finite time. We also show that the same condition holds for the search variant of DCSP. Collaterally, our results unveil a feature of the processes’ neighbourhood in a distributed network, its iterated degree, which plays a major role in the analysis. We explore this notion establishing a tight connection with the basic linear programming relaxation of a CSP., The project that gave rise to these results received the support of a fellowship from “la Caixa” Foundation (ID 100010434). The fellowship code is LCF/BQ/DI18/11660056. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No. 713673. Victor Dalmau was supported by MICCIN grants TIN2016-76573-C2-1P and PID2019-109137GB-C22.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Promise constraint satisfaction and width

  • Atserias, Albert
  • Dalmau, Víctor
Comunicació presentada a 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), celebrat del 9 al 12 de gener de 2022 de manera virtual., We study the power of the bounded-width consistency algorithm in the context of the fixed-template Promise Constraint Satisfaction Problem (PCSP). Our main technical finding is that the template of every PCSP that is solvable in bounded width satisfies a certain structural condition implying that its algebraic closure-properties include weak near unanimity polymorphisms of all large arities. While this parallels the standard (non-promise) CSP theory, the method of proof is quite different and applies even to the regime of sublinear width. We also show that, in contrast with the CSP world, the presence of weak near unanimity polymorphisms of all large arities does not guarantee solvability in bounded width. The separating example is even solvable in the second level of the Sherali-Adams (SA) hierarchy of linear programming relaxations. This shows that, unlike for CSPs, linear programming can be stronger than bounded width. A direct application of these methods also show that the problem of q-coloring p-colorable graphs is not solvable in bounded or even sublinear width, for any two constants p and q such that 3 ≤ p ≤ q. Turning to algorithms, we note that Wigderson's algorithm for O( √ n)-coloring 3-colorable graphs with n vertices is implementable in width 4. Indeed, by generalizing the method we see that, for any ∊ > 0 smaller than 1/2, the optimal width for solving the problem of O(n∊)-coloring 3-colorable graphs with n vertices lies between n1–3∊ and n1–2∊. The upper bound gives a simple exp(Θ(n1–2∊ log(n)))-time algorithm that, asymptotically, beats the straightforward exp(Θ(n1–∊)) bound that follows from partitioning the graph into O(n∊) many independent parts each of size O(n1–∊)., Albert Atserias: Partially funded by the MICIN through grant PID2019-109137GB-C22 (PROOFS) and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M). Víctor Dalmau: Partially funded by the MICIN through grant PID2019-109137GB-C22 (PROOFS).