Pasar al contenido principal

SISTEMAS DE PRUEBA MAS ALLA DE RESOLUCION: ANALISIS TEORICO

PID2019-109137GB-C22

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2019
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POMPEU FABRA CCT

Resultados relacionados

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

Repositorio Digital de la UPF
Publicación 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
Publicación 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
Publicación Artículo científico (JournalArticle)

Dismantlability, connectedness, and mixing in relational structures

  • Briceño, Raimundo
  • Bulatov, Andrei A.
  • Dalmau, Víctor
  • Larose, Benoit
The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have been shown to play a crucial role in many of those applications. For instance, in the decision CSPs, structural properties of the relational structures involved—like, for example, dismantlability—and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. Topological properties of the solution set such as connectedness are related to the hardness of CSPs over random structures. Additionally, in approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions and free energy. In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by Brightwell and Winkler, who showed that dismantlability of the target graph, connectedness of the set of homomorphisms, and good mixing properties of the corresponding spin system are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by Briceño. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by Larose, Loten, and Tardif., The first author was supported by CONICYT/FONDECYT Postdoctorado 3190191 and ERC Starting Grants 678520 and 676970. The second author was supported by an NSERC Discovery grant. The third author was supported by MICCIN grants TIN2016-76573-C2-1P and PID2019-109137GB-C22, and Maria de Maeztu Unit of Excellence Programme MDM-2015-0502. The fourth author was supported by an NSERC Discovery grant and FRQNT.
Repositorio Digital de la UPF
Publicación 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.
RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Optimality of syntactic dependency distances

  • Ferrer-i-Cancho, Ramon
  • Gómez-Rodríguez, Carlos
  • Esteban, Juan Luis
  • Alemany-Puig, Lluís
[Abstract]: It is often stated that human languages, as other biological systems, are shaped by cost-cutting pressures but, to what extent? Attempts to quantify the degree of optimality of languages by means of an optimality score have been scarce and focused mostly on English. Here we recast the problem of the optimality of the word order of a sentence as an optimization problem on a spatial network where the vertices are words, arcs indicate syntactic dependencies, and the space is defined by the linear order of the words in the sentence. We introduce a score to quantify the cognitive pressure to reduce the distance between linked words in a sentence. The analysis of sentences from 93 languages representing 19 linguistic families reveals that half of languages are optimized to a 70 % or more. The score indicates that distances are not significantly reduced in a few languages and confirms two theoretical predictions: that longer sentences are more optimized and that distances are more likely to be longer than expected by chance in short sentences. We present a hierarchical ranking of languages by their degree of optimization. The score has implications for various fields of language research (dependency linguistics, typology, historical linguistics, clinical linguistics, and cognitive science). Finally, the principles behind the design of the score have implications for network science., We are grateful to C. Bentz, N. Català, M. H. Christiansen, M. Gustison, and A. Hernández-Fernández for helpful comments. R.F.C. and L.A.P. are supported by Grant No. TIN2017-89244-R from MINECO (Ministerio de Economía, Industria y Competitividad). R.F.C. is also supported by the recognition No. 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya). L.A.P. is also supported by Secretaria d’Universitats i Recerca de la Generalitat de Catalunya and the Social European Fund. C.G.R. is supported by the European Research Council (ERC), under the European Union’s Horizon 2020 research and innovation program (FASTPARSE, Grant No. 714150), the ANSWER-ASAP project (No. TIN2017-85160-C2-1-R) and SCANNER-UDC project (No. PID2020-113230RB-C21) from ERDF/MICINN-AEI, and Xunta de Galicia (ED431C 2020/11 and an Oportunius program grant to complement ERC grants); the CITIC research center is funded by ERDF and Xunta de Galicia (ERDFGalicia 2014-2020 program, Grant No. ED431G 2019/01). J.L.E. is funded by Grants No. TIN2016-76573-C2-1-P and No. PID2019-109137GB-C22 from MINECO. R.F.C. designed the research; R.F.C and C.G.R. wrote the paper; C.G.R. collected and preprocessed data; C.G.R. and R.F.C. analyzed the data; R.F.C, C.G.R., and J.L.E developed the mathematical arguments; C.G.R., J.L.E., and L.A.P. wrote the core code; all authors verified the mathematical arguments., Xunta de Galicia; ED431C 2020/11, Xunta de Galicia; ED431G 2019/01, Agència de Gestió d'Ajuts Universitaris i de Recerca; 2017SGR-856
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Polynomial calculus for optimization

  • Bonacina, Ilario
  • Bonet, María Luisa
  • Levy, 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 the systems MaxSAT-Resolution and weighted Resolution. Unlike such systems, weighted Polynomial Calculus manipulates polynomials with coefficients in a finite field and either weights in N or Z. We show the soundness and completeness of weighted Polynomial Calculus 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 grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, IJC2018-035334-I, PID2022-138506NB-C21, and PID2022-138506NB-C22 funded by AEI., Peer reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

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

  • Bonacina, Ilario|||0000-0002-5697-8070
  • Galesi, Nicola
  • Lauria, Massimo
We introduce a novel take on sum-of-squares that is able to reason with complex numbers and still make use of polynomial inequalities. This proof system might be of independent interest since it allows to represent multivalued domains both with Boolean and Fourier encoding. We show degree and size lower bounds in this system for a natural generalization of knapsack: the vanishing sums of roots of unity. These lower bounds naturally apply to polynomial calculus as-well., The first author was supported by the Ministerio de Ciencia e Innovación MCIN/AEI/10.13039/501100011033, Spain [grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, and IJC2018-035334-I]., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Minimum projective linearizations of trees in linear time

  • Alemany Puig, Lluís|||0000-0002-3874-991X
  • Esteban Ángeles, Juan Luis|||0000-0003-0072-6576
  • Ferrer Cancho, Ramon|||0000-0002-7820-923X
The Minimum Linear Arrangement problem (MLA) consists of finding a mapping π from vertices of a graph to distinct integers that minimizes {u,v}∈E |π(u) − π(v)|. In that setting, vertices are often assumed to lie on a horizontal line and edges are drawn as semicircles above said line. For trees, various algorithms are available to solve the problem in polynomial time in n = |V |. There exist variants of the MLA in which the arrangements are constrained. Iordanskii, and later Hochberg and Stallmann (HS), put forward O(n)-time algorithms that solve the problem when arrangements are constrained to be planar (also known as one-page book embeddings). We also consider linear arrangements of rooted trees that are constrained to be projective (planar embeddings where the root is not covered by any edge). Gildea and Temperley (GT) sketched an algorithm for projective arrangements which they claimed runs in O(n) but did not provide any justification of its cost. In contrast, Park and Levy claimed that GT’s algorithm runs in O(n logdmax) where dmax is the maximum degree but did not provide sufficient detail. Here we correct an error in HS’s algorithm for the planar case, show its relationship with the projective case, and derive simple algorithms for the projective and planar cases that run without a doubt in O(n) time., 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
Publicación Artículo científico (JournalArticle)

The maximum linear arrangement problem for trees under projectivity and planarity

  • Alemany Puig, Lluís|||0000-0002-3874-991X
  • Esteban Ángeles, Juan Luis|||0000-0003-0072-6576
  • Ferrer Cancho, Ramon|||0000-0002-7820-923X
A linear arrangement is a mapping p from the n vertices of a graph G to n distinct consecutive integers. Linear arrangements can be represented by drawing the vertices along a horizontal line and drawing the edges as semicircles above said line. In this setting, the length of an edge is defined as the absolute value of the difference between the positions of its two vertices in the arrangement, and the cost of an arrangement as the sum of all edge lengths. Here we study two variants of the Maximum Linear Arrangement problem (MaxLA), which consists of finding an arrangement that maximizes the cost. In the planar variant for free trees, vertices have to be arranged in such a way that there are no edge crossings. In the projective variant for rooted trees, arrangements have to be planar and the root of the tree cannot be covered by any edge. In this paper we present algorithms that are linear in time and space to solve planar and projective MaxLA for trees. We also prove several properties of maximum projective and planar arrangements, and show that caterpillar trees maximize planar MaxLA over all trees of a fixed size thereby generalizing a previous extremal result on trees., The authors are supported by a recognition 2021SGR-Cat (01266 LQMC) from AGAUR (Generalitat de Catalunya). LAP is funded by Secretaria d’Universitats i Recerca de la Generalitat de Catalunya and the Social European Fund. JLE is funded by the grant PID2019-109137GBC22/AEI/10.13039/501100011033 from MINECO., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación 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
Publicación Artículo científico (JournalArticle)

Strength and limitations of Sherali-Adams and Nullstellensatz proof systems

  • Bonacina, Ilario|||0000-0002-5697-8070
  • Bonet Carbonell, M. Luisa|||0000-0003-1646-7177
We compare the strength of the algebraic proof systems Sherali-Adams (SA) and Nullstellensatz (NS) with Frege-style proof systems. Unlike bounded-depth Frege, SA has polynomial-size proofs of the pigeonhole principle (PHP). A natural question is whether adding PHP to bounded-depth Frege is enough to simulate SA. We show that SA, with unary integer coefficients, lies strictly between tree-like depth-1 Frege + PHP and tree-like Resolution. We introduce a levelled version of PHP (L PHP) and we show that SA with integer coefficients lies strictly between tree-like depth-1 Frege + L PHP and Resolution. Analogous results are shown for NS using the bijective (i.e. onto and functional) pigeonhole principle and a leveled version of it., This work was supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación MCIN/AEI/10.13039/501100011033, Spain [grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, IJC2018-035334-I]., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Bounds of the sum of edge lengths in linear arrangements of trees

  • Ferrer Cancho, Ramon|||0000-0002-7820-923X
  • Gómez Rodríguez, Carlos
  • Esteban Ángeles, Juan Luis|||0000-0003-0072-6576
A fundamental problem in network science is the normalization of the topological or physical distance between vertices, which requires understanding the range of variation of the unnormalized distances. Here we investigate the limits of the variation of the physical distance in linear arrangements of the vertices of trees. In particular, we investigate various problems of the sum of edge lengths in trees of a fixed size: the minimum and the maximum value of the sum for specific trees, the minimum and the maximum in classes of trees (bistar trees and caterpillar trees) and finally the minimum and the maximum for any tree. We establish some foundations for research on optimality scores for spatial networks in one dimension., RFC is supported by the grant TIN2017-89244-R from MINECO (Ministerio de Economía, Industria y Competitividad) and the recognition 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya). CGR is funded by the European Research Council (ERC), under the European Union’s Horizon 2020 research and innovation programme (FASTPARSE, grant agreement No 714150), the ANSWER-ASAP project (TIN2017-85160-C2-1-R) from MINECO and Xunta de Galicia (ED431C 2020/11, ED431G2019/01, and an Oportunius program grant to complement ERC grants). JLE is funded by the grants TIN2016-76573-C2-1-P and PID2019-109137GB-C22 from MINECO., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación 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
Publicación Artículo científico (JournalArticle)

Definable ellipsoid method, sums-of-squares proofs, and the graph isomorphism problem

  • Atserias, Albert|||0000-0002-3732-1989
  • Fijalkow, Joanna
The ellipsoid method is an algorithm that solves the (weak) feasibility and linear optimization problems for convex sets by making oracle calls to their (weak) separation problem. We observe that the previously known method for showing that this reduction can be done in fixed-point logic with counting (FPC) for linear and semidefinite programs applies to any family of explicitly bounded convex sets. We further show that the exact feasibility problem for semidefinite programs is expressible in the infinitary version of FPC. As a corollary, we get that, for the graph isomorphism problem, the Lasserre/sums-of-squares semidefinite programming hierarchy of relaxations collapses to the Sherali–Adams linear programming hierarchy, up to a small loss in the degree., The first author's research was partially supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR), MICCIN grant TIN2016-76573-C2-1P (TASSAT3), and AEI grant PID2019-109137GB-C22 (PROOFS). The work of the second author on this manuscript is part of the project BOBR that was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement 948057). The research of the second author was also supported by the French Agence Nationale de la Recherche, QUID project reference ANR-18-CE40-0031. Part of this work was done while the second author was visiting UPC, funded by AUTAR., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación 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
Publicación 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
Publicación Capítulo o parte de un libro (BookPart)

Consistency, acyclicity, and positive semirings

  • Atserias, Albert|||0000-0002-3732-1989
  • Kolaitis, Phokion
In several different settings, one comes across situations in which the objects of study are locally consistent but globally inconsistent. Earlier work about probability distributions by Vorob’ev (1962) and about database relations by Beeri et al. (1983) produced characterizations of when local consistency always implies global consistency. Towards a common generalization of these results, we consider K-relations, that is, relations over a set of attributes such that each tuple in the relation is associated with an element from an arbitrary, but fixed, positive semiring K. We introduce the notions of projection of a K-relation, consistency of two K-relations up to normalization, and global consistency of a collection of K-relations; these notions are natural extensions of the corresponding notions about probability distributions and database relations. We then show that a collection of sets of attributes has the property that every pairwise consistent collection of K-relations over those attributes is globally consistent if and only if the sets of attributes form an acyclic hypergraph. This generalizes the aforementioned results by Vorob’ev and by Beeri et al., and demonstrates that K-relations over positive semirings constitute a natural framework for the study of the interplay between local and global consistency. In the course of the proof, we introduce a notion of join of two K-relations and argue that it is the “right” generalization of the join of two database relations. Furthermore, to show that non-acyclic hypergraphs yield pairwise consistent K-relations that are globally inconsistent, we generalize a construction by Tseitin (1968) in his study of hard-to-prove tautologies in propositional logic., Albert Atserias was partially funded by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR), and by MICCIN grant PID2019-109137GB-C22 (PROOFS). Phokion Kolaitis was partially supported by NSF Grant IIS-1814152., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación 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
Publicación 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
Publicación

Consistency, acyclicity, and positive semirings

  • Atserias, Albert
  • Kolaitis, Phokion
In several different settings, one comes across situations in which the objects of study are locally consistent but globally inconsistent. Earlier work about probability distributions by Vorob’ev (1962) and about database relations by Beeri et al. (1983) produced characterizations of when local consistency always implies global consistency. Towards a common generalization of these results, we consider K-relations, that is, relations over a set of attributes such that each tuple in the relation is associated with an element from an arbitrary, but fixed, positive semiring K. We introduce the notions of projection of a K-relation, consistency of two K-relations up to normalization, and global consistency of a collection of K-relations; these notions are natural extensions of the corresponding notions about probability distributions and database relations. We then show that a collection of sets of attributes has the property that every pairwise consistent collection of K-relations over those attributes is globally consistent if and only if the sets of attributes form an acyclic hypergraph. This generalizes the aforementioned results by Vorob’ev and by Beeri et al., and demonstrates that K-relations over positive semirings constitute a natural framework for the study of the interplay between local and global consistency. In the course of the proof, we introduce a notion of join of two K-relations and argue that it is the “right” generalization of the join of two database relations. Furthermore, to show that non-acyclic hypergraphs yield pairwise consistent K-relations that are globally inconsistent, we generalize a construction by Tseitin (1968) in his study of hard-to-prove tautologies in propositional logic., Albert Atserias was partially funded by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR), and by MICCIN grant PID2019-109137GB-C22 (PROOFS). Phokion Kolaitis was partially supported by NSF Grant IIS-1814152., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación 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
Publicación Artículo científico (JournalArticle)

Minimum projective linearizations of trees in linear time

  • Alemany Puig, Lluís
  • Esteban Ángeles, Juan Luis
  • Ferrer Cancho, Ramon
The Minimum Linear Arrangement problem (MLA) consists of finding a mapping π from vertices of a graph to distinct integers that minimizes {u,v}∈E |π(u) − π(v)|. In that setting, vertices are often assumed to lie on a horizontal line and edges are drawn as semicircles above said line. For trees, various algorithms are available to solve the problem in polynomial time in n = |V |. There exist variants of the MLA in which the arrangements are constrained. Iordanskii, and later Hochberg and Stallmann (HS), put forward O(n)-time algorithms that solve the problem when arrangements are constrained to be planar (also known as one-page book embeddings). We also consider linear arrangements of rooted trees that are constrained to be projective (planar embeddings where the root is not covered by any edge). Gildea and Temperley (GT) sketched an algorithm for projective arrangements which they claimed runs in O(n) but did not provide any justification of its cost. In contrast, Park and Levy claimed that GT’s algorithm runs in O(n logdmax) where dmax is the maximum degree but did not provide sufficient detail. Here we correct an error in HS’s algorithm for the planar case, show its relationship with the projective case, and derive simple algorithms for the projective and planar cases that run without a doubt in O(n) time., 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
Publicación Artículo científico (JournalArticle)

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

  • Bonacina, Ilario
  • Galesi, Nicola
  • Lauria, Massimo
We introduce a novel take on sum-of-squares that is able to reason with complex numbers and still make use of polynomial inequalities. This proof system might be of independent interest since it allows to represent multivalued domains both with Boolean and Fourier encoding. We show degree and size lower bounds in this system for a natural generalization of knapsack: the vanishing sums of roots of unity. These lower bounds naturally apply to polynomial calculus as-well., The first author was supported by the Ministerio de Ciencia e Innovación MCIN/AEI/10.13039/501100011033, Spain [grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, and IJC2018-035334-I]., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Strength and limitations of Sherali-Adams and Nullstellensatz proof systems

  • Bonacina, Ilario
  • Bonet Carbonell, M. Luisa
We compare the strength of the algebraic proof systems Sherali-Adams (SA) and Nullstellensatz (NS) with Frege-style proof systems. Unlike bounded-depth Frege, SA has polynomial-size proofs of the pigeonhole principle (PHP). A natural question is whether adding PHP to bounded-depth Frege is enough to simulate SA. We show that SA, with unary integer coefficients, lies strictly between tree-like depth-1 Frege + PHP and tree-like Resolution. We introduce a levelled version of PHP (L PHP) and we show that SA with integer coefficients lies strictly between tree-like depth-1 Frege + L PHP and Resolution. Analogous results are shown for NS using the bijective (i.e. onto and functional) pigeonhole principle and a leveled version of it., This work was supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación MCIN/AEI/10.13039/501100011033, Spain [grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, IJC2018-035334-I]., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Bounds of the sum of edge lengths in linear arrangements of trees

  • Ferrer Cancho, Ramon
  • Gómez Rodríguez, Carlos
  • Esteban Ángeles, Juan Luis
A fundamental problem in network science is the normalization of the topological or physical distance between vertices, which requires understanding the range of variation of the unnormalized distances. Here we investigate the limits of the variation of the physical distance in linear arrangements of the vertices of trees. In particular, we investigate various problems of the sum of edge lengths in trees of a fixed size: the minimum and the maximum value of the sum for specific trees, the minimum and the maximum in classes of trees (bistar trees and caterpillar trees) and finally the minimum and the maximum for any tree. We establish some foundations for research on optimality scores for spatial networks in one dimension., RFC is supported by the grant TIN2017-89244-R from MINECO (Ministerio de Economía, Industria y Competitividad) and the recognition 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya). CGR is funded by the European Research Council (ERC), under the European Union’s Horizon 2020 research and innovation programme (FASTPARSE, grant agreement No 714150), the ANSWER-ASAP project (TIN2017-85160-C2-1-R) from MINECO and Xunta de Galicia (ED431C 2020/11, ED431G2019/01, and an Oportunius program grant to complement ERC grants). JLE is funded by the grants TIN2016-76573-C2-1-P and PID2019-109137GB-C22 from MINECO., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación Artículo científico (JournalArticle)

Definable ellipsoid method, sums-of-squares proofs, and the graph isomorphism problem

  • Atserias, Albert
  • Fijalkow, Joanna
The ellipsoid method is an algorithm that solves the (weak) feasibility and linear optimization problems for convex sets by making oracle calls to their (weak) separation problem. We observe that the previously known method for showing that this reduction can be done in fixed-point logic with counting (FPC) for linear and semidefinite programs applies to any family of explicitly bounded convex sets. We further show that the exact feasibility problem for semidefinite programs is expressible in the infinitary version of FPC. As a corollary, we get that, for the graph isomorphism problem, the Lasserre/sums-of-squares semidefinite programming hierarchy of relaxations collapses to the Sherali–Adams linear programming hierarchy, up to a small loss in the degree., The first author's research was partially supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR), MICCIN grant TIN2016-76573-C2-1P (TASSAT3), and AEI grant PID2019-109137GB-C22 (PROOFS). The work of the second author on this manuscript is part of the project BOBR that was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement 948057). The research of the second author was also supported by the French Agence Nationale de la Recherche, QUID project reference ANR-18-CE40-0031. Part of this work was done while the second author was visiting UPC, funded by AUTAR., Peer Reviewed, Postprint (published version), This is an extended full version of the paper Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem that appeared in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS' 18), 2018, pp. 66-75.
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación Artículo científico (JournalArticle)

The maximum linear arrangement problem for trees under projectivity and planarity

  • Alemany Puig, Lluís
  • Esteban Ángeles, Juan Luis
  • Ferrer Cancho, Ramon
A linear arrangement is a mapping p from the n vertices of a graph G to n distinct consecutive integers. Linear arrangements can be represented by drawing the vertices along a horizontal line and drawing the edges as semicircles above said line. In this setting, the length of an edge is defined as the absolute value of the difference between the positions of its two vertices in the arrangement, and the cost of an arrangement as the sum of all edge lengths. Here we study two variants of the Maximum Linear Arrangement problem (MaxLA), which consists of finding an arrangement that maximizes the cost. In the planar variant for free trees, vertices have to be arranged in such a way that there are no edge crossings. In the projective variant for rooted trees, arrangements have to be planar and the root of the tree cannot be covered by any edge. In this paper we present algorithms that are linear in time and space to solve planar and projective MaxLA for trees. We also prove several properties of maximum projective and planar arrangements, and show that caterpillar trees maximize planar MaxLA over all trees of a fixed size thereby generalizing a previous extremal result on trees., The authors are supported by a recognition 2021SGR-Cat (01266 LQMC) from AGAUR (Generalitat de Catalunya). LAP is funded by Secretaria d’Universitats i Recerca de la Generalitat de Catalunya and the Social European Fund. JLE is funded by the grant PID2019-109137GBC22/AEI/10.13039/501100011033 from MINECO., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación Artículo científico (JournalArticle)

Dismantlability, connectedness, and mixing in relational structures

  • Briceño, Raimundo
  • Bulatov, Andrei A.
  • Dalmau, Víctor
  • Larose, Benoit
The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have been shown to play a crucial role in many of those applications. For instance, in the decision CSPs, structural properties of the relational structures involved—like, for example, dismantlability—and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. Topological properties of the solution set such as connectedness are related to the hardness of CSPs over random structures. Additionally, in approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions and free energy. In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by Brightwell and Winkler, who showed that dismantlability of the target graph, connectedness of the set of homomorphisms, and good mixing properties of the corresponding spin system are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by Briceño. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by Larose, Loten, and Tardif., The first author was supported by CONICYT/FONDECYT Postdoctorado 3190191 and ERC Starting Grants 678520 and 676970. The second author was supported by an NSERC Discovery grant. The third author was supported by MICCIN grants TIN2016-76573-C2-1P and PID2019-109137GB-C22, and Maria de Maeztu Unit of Excellence Programme MDM-2015-0502. The fourth author was supported by an NSERC Discovery grant and FRQNT.
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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).