Skip to main content

Resultados relacionados

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

UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Proving termination through conditional termination

  • Borralleras Andreu, Cristina
  • Brockschmidt, Marc
  • Larraz Hurtado, Daniel|||0000-0001-5305-7340
  • Oliveras Llunell, Albert|||0000-0002-5893-1911
  • Rodríguez Carbonell, Enric|||0000-0003-1061-3954
  • Rubio Gimeno, Alberto|||0000-0002-0501-9830
We present a constraint-based method for proving conditional termination of integer programs. Building on this, we construct a framework to prove (unconditional) program termination using a powerful mechanism to combine conditional termination proofs. Our key insight is that a conditional termination proof shows termination for a subset of program execution states which do not need to be considered in the remaining analysis. This facilitates more effective termination as well as non-termination analyses, and allows handling loops with different execution phases naturally. Moreover, our method can deal with sequences of loops compositionally. In an empirical evaluation, we show that our implementation VeryMax outperforms state-of-the-art tools on a range of standard benchmarks., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Clique is hard on average for regular resolution

  • Atserias, Albert|||0000-0002-3732-1989
  • Bonacina, Ilario|||0000-0002-5697-8070
  • Rezende, Susanna F. de
  • Lauria, Massimo
  • Nordström, Jakob
  • Razborov, Alexander
We prove that for k ≪4√n regular resolution requires length nΩ(k) to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional nΩ(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Circular (yet sound) proofs

  • Atserias, Albert|||0000-0002-3732-1989
  • Lauria, Massimo
We introduce a new way of composing proofs in rule-based proof systems that generalizes tree-like and dag-like proofs. In the new definition, proofs are directed graphs of derived formulas, in which cycles are allowed as long as every formula is derived at least as many times as it is required as a premise. We call such proofs circular. We show that, for all sets of standard inference rules, circular proofs are sound. We first focus on the circular version of Resolution, and see that it is stronger than Resolution since, as we show, the pigeonhole principle has circular Resolution proofs of polynomial size. Surprisingly, as proof systems for deriving clauses from clauses, Circular Resolution turns out to be equivalent to Sherali-Adams, a proof system for reasoning through polynomial inequalities that has linear programming at its base. As corollaries we get: (1) polynomial-time (LP-based) algorithms that find circular Resolution proofs of constant width, (2) examples that separate circular from dag-like Resolution, such as the pigeonhole principle and its variants, and (3) exponentially hard cases for circular Resolution. Contrary to the case of circular resolution, for Frege we show that circular proofs can be converted into tree-like ones with at most polynomial overhead., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Feasible interpolation for polynomial calculus and sums-of-squares

  • Hakoniemi, Tuomas Antero
We prove that both Polynomial Calculus and Sums-of-Squares proof systems admit a strong form of feasible interpolation property for sets of polynomial equality constraints. Precisely, given two sets P(x, z) and Q(y, z) of equality constraints, a refutation Π of P(x, z) ∪ Q(y, z), and any assignment a to the variables z, one can find a refutation of P(x, a) or a refutation of Q(y, a) in time polynomial in the length of the bit-string encoding the refutation Π. For Sums-of-Squares we rely on the use of Boolean axioms, but for Polynomial Calculus we do not assume their presence., 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 MICCIN grant TIN2016-76573-C2-1P (TASSAT3)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

On zero-one and convergence laws for graphs embeddable on a fixed surface

  • Atserias, Albert|||0000-0002-3732-1989
  • Kreutzer, Stephan
  • Noy Serrano, Marcos|||0000-0002-2399-1359
We show that for no surface except for the plane does monadic second-order logic (MSO) have a zero-one-law - and not even a convergence law - on the class of (connected) graphs embeddable on the surface. In addition we show that every rational in [0,1] is the limiting probability of some MSO formula. This strongly refutes a conjecture by Heinig et al. (2014) who proved a convergence law for planar graphs, and a zero-one law for connected planar graphs, and also identified the so-called gaps of [0,1]: the subintervals that are not limiting probabilities of any MSO formula. The proof relies on a combination of methods from structural graph theory, especially large face-width embeddings of graphs on surfaces, analytic combinatorics, and finite model theory, and several parts of the proof may be of independent interest. In particular, we identify precisely the properties that make the zero-one law work on planar graphs but fail for every other surface., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Some subsystems of constant-depth Frege with parity

  • Garlik, Michal
  • Kolodziejczyk, Andrzej
We consider three relatively strong families of subsystems of AC0[2]-Frege proof systems, i.e., propositional proof systems using constant-depth formulas with an additional parity connective, for which exponential lower bounds on proof size are known. In order of increasing strength, the subsystems are (i) constant-depth proof systems with parity axioms and the (ii) treelike and (iii) daglike versions of systems introduced by Krajíček which we call PKcd(⊕). In a PKcd(⊕)-proof, lines are disjunctions (cedents) in which all disjuncts have depth at most d, parities can only appear as the outermost connectives of disjuncts, and all but c disjuncts contain no parity connective at all. We prove that treelike PKO(1)O(1)(⊕) is quasipolynomially but not polynomially equivalent to constant-depth systems with parity axioms. We also verify that the technique for separating parity axioms from parity connectives due to Impagliazzo and Segerlind can be adapted to give a superpolynomial separation between daglike PKO(1)O(1)(⊕) and AC0[2]-Frege; the technique is inherently unable to prove superquasipolynomial separations. We also study proof systems related to the system Res-Lin introduced by Itsykson and Sokolov. We prove that an extension of treelike Res-Lin is polynomially simulated by a system related to daglike PKO(1)O(1)(⊕), and obtain an exponential lower bound for this system., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Trade-offs between time and memory in a tighter model of CDCL SAT solvers

  • Elffers, J.
  • Johannsen, Jan
  • Lauria, Massimo
  • Magnard, Thomas
  • Nordström, Jakob
  • Vinyals, Marc
"The final publication is available at http://link.springer.com/chapter/10.1007/978-3-319-40970-2_11, A long line of research has studied the power of conflict- driven clause learning (CDCL) and how it compares to the resolution proof system in which it searches for proofs. It has been shown that CDCL can polynomially simulate resolution even with an adversarially chosen learning scheme as long as it is asserting. However, the simulation only works under the assumption that no learned clauses are ever forgot- ten, and the polynomial blow-up is significant. Moreover, the simulation requires very frequent restarts, whereas the power of CDCL with less frequent or entirely without restarts remains poorly understood. With a view towards obtaining results with tighter relations between CDCL and resolution, we introduce a more fine-grained model of CDCL that cap- tures not only time but also memory usage and number of restarts. We show how previously established strong size-space trade-offs for resolution can be transformed into equally strong trade-offs between time and memory usage for CDCL, where the upper bounds hold for CDCL with- out any restarts using the standard 1UIP clause learning scheme, and the (in some cases tightly matching) lower bounds hold for arbitrarily frequent restarts and arbitrary clause learning schemes., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Generalized satisfiability problems via operator assignments

  • Atserias, Albert|||0000-0002-3732-1989
  • Kolaitis, Phokion
  • Severini, Simone
Schaefer introduced a framework for generalized satisfiability problems on the Boolean domain and characterized the computational complexity of such problems. We investigate an algebraization of Schaefer's framework in which the Fourier transform is used to represent constraints by multilinear polynomials in a unique way. This representation of constraints gives rise to a relaxation of the notion of satisfiability in which the values to variables are linear operators on some Hilbert space. For constraints given by a system of linear equations over the two-element field, earlier work in the foundations of quantum mechanics has shown that there are systems that have no solutions in the Boolean domain, but have solutions via operator assignments on some finite-dimensional Hilbert space. Our main result is a complete characterization of the classes of Boolean relations for which there is a gap between satisfiability in the Boolean domain and the relaxation of satisfiability via operator assignments., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Co-occurrence patterns in diagnostic data

  • Piceno Cabrera, Marie Ely
  • Rodríguez Navas, Laura
  • Balcázar Navarro, José Luis|||0000-0003-4248-4528
We demonstrate how graph decomposition techniques can be employed for the visualization of hierarchical co-occurrence patterns between medical data items. Our research is based on Gaifman graphs (a mathematical concept introduced in Logic), on specific variants of this concept, and on existing graph decomposition notions, specifically, graph modules and the clan decomposition of so-called 2-structures. The construction of the Gaifman graphs from a dataset is based on co-occurrence, or lack of it, of items in the dataset. We may select a discretization on the edge labels to aim at one among several Gaifman graph variants. Then, the decomposition of the graph may provide us with visual information about the data co-occurrences, after which one can proceed to more traditional statistical analysis., Partially supported by European Research Council (ERC) under the European Union's Horizon2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR);by grant TIN2017-89244-R from Ministerio de Economia, Industria y Competitividad, and byConacyt (México). We acknowledge unfunded recognition 2017SGR-856 (MACDA) from AGAUR(Generalitat de Catalunya)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Quantum and non-signalling graph isomorphisms

  • Atserias, Albert|||0000-0002-3732-1989
  • Mancinska, Laura
  • Roberson, David E.
  • Samal, Robert
  • Severini, Simone
  • Varvitsiotis, Antonios
We introduce the (G,H)-isomorphism game, a new two-player non-local game that classical players can win with certainty iff the graphs G and H are isomorphic. We then define quantum and non-signalling isomorphisms by considering perfect quantum and non-signalling strategies for this game. We prove that non-signalling isomorphism coincides with fractional isomorphism, giving the latter an operational interpretation. We show that quantum isomorphism is equivalent to the feasibility of two polynomial systems obtained by relaxing standard integer programs for graph isomorphism to Hermitian variables. Finally, we provide a reduction from linear binary constraint system games to isomorphism games. This reduction provides examples of quantum isomorphic graphs that are not isomorphic, implies that the tensor product and commuting operator frameworks result in different notions of quantum isomorphism, and proves that both relations are undecidable., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Non-homogenizable classes of finite structures

  • Atserias, Albert|||0000-0002-3732-1989
  • Torunczyk, Szymon Abram
Homogenization is a powerful way of taming a class of finite structures with several interesting applications in different areas, from Ramsey theory in combinatorics to constraint satisfaction problems (CSPs) in computer science, through (finite) model theory. A few sufficient conditions for a class of finite structures to allow homogenization are known, and here we provide a necessary condition. This lets us show that certain natural classes are not homogenizable: 1) the class of locally consistent systems of linear equations over the two-element field or any finite Abelian group, and 2) the class of finite structures that forbid homomorphisms from a specific MSO-definable class of structures of treewidth two. In combination with known results, the first example shows that, up to pp-interpretability, the CSPs that are solvable by local consistency methods are distinguished from the rest by the fact that their classes of locally consistent instances are homogenizable. The second example shows that, for MSO-definable classes of forbidden patterns, treewidth one versus two is the dividing line to homogenizability., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Definable inapproximability: new challenges for duplicator

  • Atserias, Albert|||0000-0002-3732-1989
  • Dawar, Anuj
We consider the hardness of approximation of optimization problems from the point of view of definability. For many NP-hard optimization problems it is known that, unless P=NP, no polynomial-time algorithm can give an approximate solution guaranteed to be within a fixed constant factor of the optimum. We show, in several such instances and without any complexity theoretic assumption, that no algorithm that is expressible in fixed-point logic with counting (FPC) can compute an approximate solution. Since important algorithmic techniques for approximation algorithms (such as linear or semidefinite programming) are expressible in FPC, this yields lower bounds on what can be achieved by such methods. The results are established by showing lower bounds on the number of variables required in first-order logic with counting to separate instances with a high optimum from those with a low optimum for fixed-size instances., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A remark on pseudo proof systems and hard instances of the satisfiability problem

  • Maly, Jan
  • Muller, Moritz Martin
We link two concepts from the literature, namely hard sequences for the satisfiability problem sat and so-called pseudo proof systems proposed for study by Krajícek. Pseudo proof systems are elements of a particular nonstandard model constructed by forcing with random variables. We show that the existence of mad pseudo proof systems is equivalent to the existence of a randomized polynomial time procedure with a highly restrictive use of randomness which produces satisfiable formulas whose satisfying assignments are probably hard to find., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Homomorphism problems for first-order definable structures

  • Klin, Bartek
  • Lasota, Slawomir
  • Ochremiak, Joanna Regina
  • Torunczyk, Szymon Abram
We investigate several variants of the homomorphism problem: given two relational structures, is there a homomorphism from one to the other? The input structures are possibly infinite, but definable by first-order interpretations in a fixed structure. Their signatures can be either finite or infinite but definable. The homomorphisms can be either arbitrary, or definable with parameters, or definable without parameters. For each of these variants, we determine its decidability status., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Clique is hard on average for regular resolution

  • Atserias, Albert|||0000-0002-3732-1989
  • Bonacina, Ilario|||0000-0002-5697-8070
  • De Rezende, Susanna F.
  • Lauria, Massimo
  • Nordström, Jakob
  • Razborov, Alexander
We prove that for k ≪ 4√n regular resolution requires length nΩ(k) to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent and also implies unconditional nΩ(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs., The first, second, and fourth authors were supported by the European Research Council under the European Union’s Horizon 2020 Research and Innovation Programme/ERC grant agreement no. 648276 AUTAR. The third and fifth authors were supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007–2013)/ ERC grant agreement no. 279611 as well as by Swedish Research Council grants 621-2012-5645 and 2016-00782, and the second author did part of this work while at KTH Royal Institute of Technology supported by the same grants. The last author was supported by the Russian Foundation for Basic Research., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Relative entailment among probabilistic implications

  • Atserias, Albert|||0000-0002-3732-1989
  • Balcázar Navarro, José Luis|||0000-0003-4248-4528
  • Piceno Cabrera, Marie Ely
We study a natural variant of the implicational fragment of propositional logic. Its formulas are pairs of conjunctions of positive literals, related together by an implicational-like connective; the semantics of this sort of implication is defined in terms of a threshold on a conditional probability of the consequent, given the antecedent: we are dealing with what the data analysis community calls confidence of partial implications or association rules. Existing studies of redundancy among these partial implications have characterized so far only entailment from one premise and entailment from two premises, both in the stand-alone case and in the case of presence of additional classical implications (this is what we call "relative entailment"). By exploiting a previously noted alternative view of the entailment in terms of linear programming duality, we characterize exactly the cases of entailment from arbitrary numbers of premises, again both in the stand-alone case and in the case of presence of additional classical implications. As a result, we obtain decision algorithms of better complexity; additionally, for each potential case of entailment, we identify a critical confidence threshold and show that it is, actually, intrinsic to each set of premises and antecedent of the conclusion., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Trees whose even-degree vertices induce a path are antimagic

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Tey Carrera, Joaquín
An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . . , |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic; however the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Anti-magic labeling of trees, Discrete Math. 331 (2014) 9–14]., A. Lozano is 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); M. Mora is supported by projects Gen. Cat. DGR 2017SGR1336, MINECO MTM2015-63791-R, and H2020-MSCARISE project 734922-CONNECT; and C. Seara is supported by projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and H2020-MSCARISE project 734922-CONNECT., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Definable inapproximability: New challenges for duplicator

  • Atserias, Albert|||0000-0002-3732-1989
  • Dawar, Anuj
We consider the hardness of approximation of optimization problems from the point of view of definability. For many NP-hard optimization problems it is known that, unless P = NP, no polynomial-time algorithm can give an approximate solution guaranteed to be within a fixed constant factor of the optimum. We show, in several such instances and without any complexity theoretic assumption, that no algorithm that is expressible in fixed-point logic with counting (FPC) can compute an approximate solution. Since important algorithmic techniques for approximation algorithms (such as linear or semidefinite programming) are expressible in FPC, this yields lower bounds on what can be achieved by such methods. The results are established by showing lower bounds on the number of variables required in first-order logic with counting to separate instances with a high optimum from those with a low optimum for fixed-size instances., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Automating resolution is NP-Hard

  • Atserias, Albert|||0000-0002-3732-1989
  • Muller, Moritz Martin
We show that the problem of finding a Resolution refutation that is at most polynomially longer than a shortest one is NP-hard. In the parlance of proof complexity, Resolution is not automatable unless P = NP. Indeed, we show that it is NP-hard to distinguish between formulas that have Resolution refutations of polynomial length and those that do not have subexponential length refutations. This also implies that Resolution is not automatable in subexponential time or quasi-polynomial time unless NP is included in SUBEXP or QP, respectively., Both authors were 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). First author partially funded by MICCIN grant TIN2016-76573-C2-1P (TASSAT3)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Resolution lower bounds for refutation statements

  • Garlik, Michal
For any unsatisfiable CNF formula we give an exponential lower bound on the size of resolutionrefutations of a propositional statement that the formula has a resolution refutation. We describethree applications. (1) An open question in [2] asks whether a certain natural propositional encodingof the above statement is hard for Resolution. We answer by giving an exponential size lower bound.(2) We show exponential resolution size lower bounds for reflection principles, thereby improvinga result in [1]. (3) We provide new examples of CNFs that exponentially separate Res(2) fromResolution (an exponential separation of these two proof systems was originally proved in [10])., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The parameterized space complexity of model-checking bounded variable first-order logic

  • Chen, Yijia
  • Elberfeld, Michael
  • Muller, Moritz Martin
The parameterized model-checking problem for a class of first-order sentences (queries) asks to decide whether a given sentence from the class holds true in a given relational structure (database); the parameter is the length of the sentence. We study the parameterized space complexity of the model-checking problem for queries with a bounded number of variables. For each bound on the quantifier alternation rank the problem becomes complete for the corresponding level of what we call the tree hierarchy, a hierarchy of parameterized complexity classes defined via space bounded alternating machines between parameterized logarithmic space and fixed-parameter tractable time. We observe that a parameterized logarithmic space model-checker for existential bounded variable queries would allow to improve Savitch's classical simulation of nondeterministic logarithmic space in deterministic space O(log2n). Further, we define a highly space efficient model-checker for queries with a bounded number of variables and bounded quantifier alternation rank. We study its optimality under the assumption that Savitch's Theorem is optimal., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

Trees whose even-degree vertices induce a path are antimagic

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Tey Carrera, Joaquín
An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . . , |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic; however, the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Discrete Math. 331 (2014) 9–14].
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Limiting probabilities of first order properties of random sparse graphs and hypergraphs

  • Larrauri Borroto, Lázaro Alberto
  • Müller, Tobias
  • Noy Serrano, Marcos|||0000-0002-2399-1359
"This is the peer reviewed version of the following article: Larrauri, L.; Müller, T.; Noy, M. Limiting probabilities of first order properties of random sparse graphs and hypergraphs. "Random structures and algorithms", 18 Agost 2021, vol. 60, núm. 3, p. 506-526., which has been published in final form at https://onlinelibrary.wiley.com/doi/10.1002/rsa.21041. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. This article may not be enhanced, enriched or otherwise transformed into a derivative work, without express permission from Wiley or by statutory rights under applicable legislation. Copyright notices must not be removed, obscured or modified. The article must be linked to Wiley’s version of record on Wiley Online Library and any embedding, framing or otherwise making available the article or pages thereof by third parties from platforms, services and websites other than Wiley Online Library must be prohibited.", Let Gn be the binomial random graph G(n, p = c/n) in the sparse regime, which as is well-known undergoes a phase transition at c = 1. Lynch (Random Structures Algorithms, 1992) showed that for every first order sentence f, the limiting probability that Gn satisfies f as n ¿ 8 exists, and moreover it is an analytic function of c. In this paper we consider the closure Lc in [0, 1] of the set Lc of all limiting probabilities of first order sentences in Gn. We show that there exists a critical value c0 ˜ 0.93 such that Lc = [0, 1] when c = c0, whereas Lc misses at least one subinterval when c < c0. We extend these results to random d-uniform sparse hypergraphs, where the probability of a hyperedge is given by p = c/nd-1 ., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Distinguishing tournaments with small label classes

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
A d-distinguishing vertex (arc) labeling of a digraph is a vertex (arc) labeling using d labels that is not preserved by any nontrivial automorphism. Let ρ(T) (ρ′(T)) be the minimum size of a label class in a 2-distinguishing vertex (arc) labeling of a tournament T. Gluck's Theorem implies that ρ(T) ≤ ⌊n/2⌋ for any tournament T of order n. We construct a family of tournaments ℌ such that ρ(T) ≥ ⌊n/2⌋ for any tournament of order n in ℌ. Additionally, we prove that ρ′(T) ≤ ⌊7n/36⌋ + 3 for any tournament T of order n and ρ′(T) ≥ ⌈n/6⌉ when T ∈ ℌ and has order n. These results answer some open questions stated by Boutin., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication Contribución de congreso (ConferenceOutput)

On the power of symmetric linear programs

  • Atserias, Albert|||0000-0002-3732-1989
  • Dawar, Anuj
  • Ochremiak, Joanna
© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991) showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication Artículo científico (JournalArticle)

On the power of symmetric linear programs

  • Atserias, Albert|||0000-0002-3732-1989
  • Dawar, Anuj
  • Ochremiak, Joanna Regina
We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs, while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991), showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem., First author 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 MICCIN grant TIN2016-76573-C2-1P (TASSAT3). The second author was partially supported by a Fellowship of the Alan Turing Institute under the EPSRC grant EP/N510129/1. The third author funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 795936., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Circular (yet sound) proofs in propositional logic

  • Atserias, Albert|||0000-0002-3732-1989
  • Lauria, Massimo
Proofs in propositional logic are typically presented as trees of derived formulas or, alternatively, as directed acyclic graphs of derived formulas. This distinction between tree-like vs. dag-like structure is particularly relevant when making quantitative considerations regarding, for example, proof size. Here we analyze a more general type of structural restriction for proofs in rule-based proof systems. In this definition, proofs are directed graphs of derived formulas in which cycles are allowed as long as every formula is derived at least as many times as it is required as a premise. We call such proofs “circular”. We show that, for all sets of standard inference rules with single or multiple conclusions, circular proofs are sound. We start the study of the proof complexity of circular proofs at Circular Resolution, the circular version of Resolution. We immediately see that Circular Resolution is stronger than dag-like Resolution since, as we show, the propositional encoding of the pigeonhole principle has circular Resolution proofs of polynomial size. Furthermore, for derivations of clauses from clauses, we show that Circular Resolution is, surprisingly, equivalent to Sherali-Adams, a proof system for reasoning through polynomial inequalities that has linear programming at its base. As corollaries we get: (1) polynomial-time (LP-based) algorithms that find Circular Resolution proofs of constant width, (2) examples that separate Circular from dag-like Resolution, such as the pigeonhole principle and its variants, and (3) exponentially hard cases for Circular Resolution. Contrary to the case of Circular Resolution, for Frege we show that circular proofs can be converted into tree-like proofs with at most polynomial overhead., Albert Atserias and Massimo Lauria were 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). Albert Atserias partially funded by MINECO through TIN2013-48031-C4-1-P (TASSAT2)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Size-degree trade-offs for Sums-of-Squares and Positivstellensatz proofs

  • Atserias, Albert|||0000-0002-3732-1989
  • Hakoniemi, Tuomas Antero
We show that if a system of degree-k polynomial constraints on n Boolean variables has a Sums-of-Squares (SOS) proof of unsatisfiability with at most s many monomials, then it also has one whose degree is of the order of the square root of n log s plus k. A similar statement holds for the more general Positivstellensatz (PS) proofs. This establishes size-degree trade-offs for SOS and PS that match their analogues for weaker proof systems such as Resolution, Polynomial Calculus, and the proof systems for the LP and SDP hierarchies of Lovász and Schrijver. As a corollary to this, and to the known degree lower bounds, we get optimal integrality gaps for exponential size SOS proofs for sparse random instances of the standard NP-hard constraint optimization problems. We also get exponential size SOS lower bounds for Tseitin and Knapsack formulas. The proof of our main result relies on a zero-gap duality theorem for pre-ordered vector spaces that admit an order unit, whose specialization to PS and SOS may be of independent interest., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Probabilities of first-order sentences on sparse random relational structures: An application to definability on random CNF formulas

  • Larrauri Borroto, Lázaro Alberto
We extend the convergence law for sparse random graphs proven by Lynch to arbitrary relational languages. We consider a finite relational vocabulary s and a first-order theory T for s composed of symmetry and anti-reflexivity axioms. We define a binomial random model of finite s-structures that satisfy T and show that first-order properties have well defined asymptotic probabilities when the expected number of tuples satisfying each relation in s is linear. It is also shown that these limit probabilities are well behaved with respect to several parameters that represent the density of tuples in each relation R in the vocabulary s¿. An application of these results to the problem of random Boolean satisfiability is presented. We show that in a random k-CNF formula on n variables, where each possible clause occurs with probability ~c/nk-1¿, independently any first-order property of k-CNF formulas that implies unsatisfiability does almost surely not hold as n tends to infinity., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Incomplete SMT techniques for solving non-linear formulas over the integers

  • Borralleras Andreu, Cristina
  • Larraz Hurtado, Daniel|||0000-0001-5305-7340
  • Rodríguez Carbonell, Enric|||0000-0003-1061-3954
  • Oliveras Llunell, Albert|||0000-0002-5893-1911
  • Rubio Gimeno, Alberto|||0000-0002-0501-9830
We present new methods for solving the Satisfiability Modulo Theories problem over the theory of QuantifierFree Non-linear Integer Arithmetic, SMT(QF-NIA), which consists of deciding the satisfiability of ground formulas with integer polynomial constraints. Following previous work, we propose to solve SMT(QF-NIA) instances by reducing them to linear arithmetic: non-linear monomials are linearized by abstracting them with fresh variables and by performing case splitting on integer variables with finite domain. For variables that do not have a finite domain, we can artificially introduce one by imposing a lower and an upper bound and iteratively enlarge it until a solution is found (or the procedure times out). The key for the success of the approach is to determine, at each iteration, which domains have to be enlarged. Previously, unsatisfiable cores were used to identify the domains to be changed, but no clue was obtained as to how large the new domains should be. Here, we explain two novel ways to guide this process by analyzing solutions to optimization problems: (i) to minimize the number of violated artificial domain bounds, solved via a Max-SMT solver, and (ii) to minimize the distance with respect to the artificial domains, solved via an Optimization Modulo Theories (OMT) solver. Using this SMT-based optimization technology allows smoothly extending the method to also solve Max-SMT problems over non-linear integer arithmetic. Finally, we leverage the resulting Max-SMT(QF-NIA) techniques to solve ∃∀ formulas in a fragment of quantified non-linear arithmetic that appears commonly in verification and synthesis applications., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

A parameterized halting problem, the linear time hierarchy, and the MRDP theorem

  • Chen, Yijia
  • Muller, Moritz Martin
  • Yokoyama, Keita
The complexity of the parameterized halting problem for nondeterministic Turing machines p-Halt is known to be related to the question of whether there are logics capturing various complexity classes [10]. Among others, if p-Halt is in para-AC0, the parameterized version of the circuit complexity class AC0, then AC0, or equivalently, (+, x)-invariant FO, has a logic. Although it is widely believed that p-Halt ∉. para-AC0, we show that the problem is hard to settle by establishing a connection to the question in classical complexity of whether NE ⊈ LINH. Here, LINH denotes the linear time hierarchy. On the other hand, we suggest an approach toward proving NE ⊈ LINH using bounded arithmetic. More specifically, we demonstrate that if the much celebrated MRDP (for Matiyasevich-Robinson-Davis-Putnam) theorem can be proved in a certain fragment of arithmetic, then NE ⊈ LINH. Interestingly, central to this result is a para-AC0 lower bound for the parameterized model-checking problem for FO on arithmetical structures., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Proof complexity meets algebra

  • Atserias, Albert|||0000-0002-3732-1989
  • Ochremiak, Joanna
We analyse how the standard reductions between constraint satisfaction problems affect their proof complexity. We show that, for the most studied propositional and semi-algebraic proof systems, the classical constructions of pp-interpretability, homomorphic equivalence and addition of constants to a core preserve the proof complexity of the CSP. As a result, for those proof systems, the classes of constraint languages for which small unsatisfiability certificates exist can be characterised algebraically. We illustrate our results by a gap theorem saying that a constraint language either has resolution refutations of bounded width, or does not have bounded-depth Frege refutations of subexponential size. The former holds exactly for the widely studied class of constraint languages of bounded width. This class is also known to coincide with the class of languages with Sums-of-Squares refutations of sublinear degree, a fact for which we provide an alternative proof. We hence ask for the existence of a natural proof system with good behaviour with respect to reductions and simultaneously small size refutations beyond bounded width. We give an example of such a proof system by showing that bounded-degree Lovasz-Schrijver satisfies both requirements., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Antimagic labelings of caterpillars

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Seara Ojea, Carlos|||0000-0002-0095-1725
A k-antimagic labeling of a graph G is an injection from E(G) to {1,2, ..., |E(G)|+k} such that all vertex sums are pairwise distinct, where the vertex sum at vertex u is the sum of the labels assigned to edges incident to u. We call a graph k-antimagic when it has a k-antimagic labeling, and antimagic when it is 0-antimagic. Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic, but the conjecture is still open even for trees. Here we study k-antimagic labelings of caterpillars. We use algorithmic and constructive techniques, instead of the standard Combinatorial NullStellenSatz method, to prove our results: (i) any caterpillar of order n is (⌊(n−1)/2⌋−2)-antimagic; (ii) any caterpillar with a spine of order s with either at least ⌊(3s+1)/2⌋ leaves or ⌊(s−1)/2⌋ consecutive vertices of degree at most 2 at one end of a longest path, is antimagic; and (iii) if p is a prime number, any caterpillar with a spine of order p, p−1 or p−2 is 1-antimagic., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Feasibly constructive proofs of succinct weak circuit lower bounds

  • Muller, Moritz Martin
  • Pich, Ján
We ask for feasibly constructive proofs of known circuit lower bounds for explicit functions on bit strings of length n. In 1995 Razborov showed that many can be proved in PV1, a bounded arithmetic formalizing polynomial time reasoning. He formalized circuit lower bound statements for small n of doubly logarithmic order. It is open whether PV1 proves known lower bounds in succinct formalizations for n of logarithmic order. We give such proofs in APC1, an extension of PV1 formalizing probabilistic polynomial time reasoning: for parity and AC0, for mod q and AC0[p] (only for n slightly smaller than logarithmic), and for k-clique and monotone circuits. We also formalize Razborov and Rudich’s natural proof barrier. We ask for short propositional proofs of circuit lower bounds expressed succinctly by propositional formulas of size nO(1) or at least much smaller than the 2O(n) size of the common “truth table” formula. We discuss two such expressions: one via feasible functions witnessing errors of circuits, and one via the anticheckers of Lipton and Young 1994. Our APC1 formalizations yield conditional upper bounds for the succinct formulas obtained by witnessing: we get short Extended Frege proofs from general circuit lower bounds expressed by the common “truth-table” formulas. We also show how to construct in quasipolynomial time propositional proofs of quasipolynomial size tautologies expressing AC0[p] quasipolynomial size lower bounds; these proofs are in Jerábek’s system WF., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Polynomial time ultrapowers and the consistency of circuit lower bounds

  • Bydžovský, Jan
  • Muller, Moritz Martin
A polynomial time ultrapower is a structure given by the set of polynomial time computable functions modulo some ultrafilter. They model the universal theory ∀PV of all polynomial time functions. Generalizing a theorem of Hirschfeld (Israel J Math 20(2):111–126, 1975), we show that every countable model of ∀PV is isomorphic to an existentially closed substructure of a polynomial time ultrapower. Moreover, one can take a substructure of a special form, namely a limit polynomial time ultrapower in the classical sense of Keisler (in: Bergelson, V., Blass, A., Di Nasso, M., Jin, R. (eds.) Ultrafilters across mathematics, contemporary mathematics vol 530, pp 163–179. AMS, New York, 1963). Using a polynomial time ultrapower over a nonstandard Herbrand saturated model of ∀PV we show that ∀PV is consistent with a formal statement of a polynomial size circuit lower bound for a polynomial time computable function. This improves upon a recent result of Krajíček and Oliveira (Logical methods in computer science 13 (1:4), 2017)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Caterpillars are antimagic

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Tey Carrera, Joaquín
An antimagic labeling of a graph G is a bijection from the set of edges E(G) to {1,2,…,|E(G)|}, such that all vertex sums are pairwise distinct, where the vertex sum at vertex u is the sum of the labels assigned to the edges incident to u. A graph is called antimagic when it has an antimagic labeling. Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic and the conjecture remains open even for trees. Here, we prove that caterpillars are antimagic by means of an O(nlogn) algorithm., Antoni Lozano is 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). Mercè Mora is supported by projects Gen. Cat. DGR 2017SGR1336, MINECO MTM2015-63791-R, and H2020-MSCA-RISE project 734922-CONNECT. Carlos Seara is supported by projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and H2020-MSCA-RISE project 734922-CONNECT. Joaquin Tey is supported by project PRODEP-12612731., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Automating Resolution is NP-hard

  • Atserias, Albert|||0000-0002-3732-1989
  • Muller, Moritz Martin
We show that the problem of finding a Resolution refutation that is at most polynomially longer than a shortest one is NP-hard. In the parlance of proof complexity, Resolution is not automatizable unless P = NP. Indeed, we show that it is NP-hard to distinguish between formulas that have Resolution refutations of polynomial length and those that do not have subexponential length refutations. This also implies that Resolution is not automatizable in subexponential time or quasi-polynomial time unless~NP is included in SUBEXP or QP, respectively., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Proof complexity meets algebra

  • Atserias, Albert|||0000-0002-3732-1989
  • Ochremiak, Joanna
We analyze how the standard reductions between constraint satisfaction problems affect their proof complexity. We show that, for the most studied propositional, algebraic, and semialgebraic proof systems, the classical constructions of pp-interpretability, homomorphic equivalence, and addition of constants to a core preserve the proof complexity of the CSP. As a result, for those proof systems, the classes of constraint languages for which small unsatisfiability certificates exist can be characterized algebraically. We illustrate our results by a gap theorem saying that a constraint language either has resolution refutations of constant width or does not have bounded-depth Frege refutations of subexponential size. The former holds exactly for the widely studied class of constraint languages of bounded width. This class is also known to coincide with the class of languages with refutations of sublinear degree in Sums of Squares and Polynomial Calculus over the real field, for which we provide alternative proofs. We then ask for the existence of a natural proof system with good behavior with respect to reductions and simultaneously small-size refutations beyond bounded width. We give an example of such a proof system by showing that bounded-degree Lovász-Schrijver satisfies both requirements. Finally, building on the known lower bounds, we demonstrate the applicability of the method of reducibilities and construct new explicit hard instances of the graph three-coloring problem for all studied proof systems., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

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

  • Atserias, Albert|||0000-0002-3732-1989
  • Ochremiak, 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 use this observation to 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. © 2018 ACM., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Limiting probabilities of first order properties of random sparse graphs and hypergraphs

  • Larrauri Borroto, Lázaro Alberto
  • Müller, Tobias
  • Noy Serrano, Marcos
"This is the peer reviewed version of the following article: Larrauri, L.; Müller, T.; Noy, M. Limiting probabilities of first order properties of random sparse graphs and hypergraphs. "Random structures and algorithms", 18 Agost 2021, vol. 60, núm. 3, p. 506-526., which has been published in final form at https://onlinelibrary.wiley.com/doi/10.1002/rsa.21041. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. This article may not be enhanced, enriched or otherwise transformed into a derivative work, without express permission from Wiley or by statutory rights under applicable legislation. Copyright notices must not be removed, obscured or modified. The article must be linked to Wiley’s version of record on Wiley Online Library and any embedding, framing or otherwise making available the article or pages thereof by third parties from platforms, services and websites other than Wiley Online Library must be prohibited.", Let Gn be the binomial random graph G(n, p = c/n) in the sparse regime, which as is well-known undergoes a phase transition at c = 1. Lynch (Random Structures Algorithms, 1992) showed that for every first order sentence f, the limiting probability that Gn satisfies f as n ¿ 8 exists, and moreover it is an analytic function of c. In this paper we consider the closure Lc in [0, 1] of the set Lc of all limiting probabilities of first order sentences in Gn. We show that there exists a critical value c0 ˜ 0.93 such that Lc = [0, 1] when c = c0, whereas Lc misses at least one subinterval when c < c0. We extend these results to random d-uniform sparse hypergraphs, where the probability of a hyperedge is given by p = c/nd-1 ., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

On zero-one and convergence laws for graphs embeddable on a fixed surface

  • Atserias, Albert
  • Kreutzer, Stephan
  • Noy Serrano, Marcos
We show that for no surface except for the plane does monadic second-order logic (MSO) have a zero-one-law - and not even a convergence law - on the class of (connected) graphs embeddable on the surface. In addition we show that every rational in [0,1] is the limiting probability of some MSO formula. This strongly refutes a conjecture by Heinig et al. (2014) who proved a convergence law for planar graphs, and a zero-one law for connected planar graphs, and also identified the so-called gaps of [0,1]: the subintervals that are not limiting probabilities of any MSO formula. The proof relies on a combination of methods from structural graph theory, especially large face-width embeddings of graphs on surfaces, analytic combinatorics, and finite model theory, and several parts of the proof may be of independent interest. In particular, we identify precisely the properties that make the zero-one law work on planar graphs but fail for every other surface., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication

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
Publication Artículo científico (JournalArticle)

Clique is hard on average for regular resolution

  • Atserias, Albert
  • Bonacina, Ilario
  • De Rezende, Susanna F.
  • Lauria, Massimo
  • Nordström, Jakob
  • Razborov, Alexander
We prove that for k ≪ 4√n regular resolution requires length nΩ(k) to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent and also implies unconditional nΩ(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs., The first, second, and fourth authors were supported by the European Research Council under the European Union’s Horizon 2020 Research and Innovation Programme/ERC grant agreement no. 648276 AUTAR. The third and fifth authors were supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007–2013)/ ERC grant agreement no. 279611 as well as by Swedish Research Council grants 621-2012-5645 and 2016-00782, and the second author did part of this work while at KTH Royal Institute of Technology supported by the same grants. The last author was supported by the Russian Foundation for Basic Research., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Definable inapproximability: new challenges for duplicator

  • Atserias, Albert
  • Dawar, Anuj
We consider the hardness of approximation of optimization problems from the point of view of definability. For many NP-hard optimization problems it is known that, unless P=NP, no polynomial-time algorithm can give an approximate solution guaranteed to be within a fixed constant factor of the optimum. We show, in several such instances and without any complexity theoretic assumption, that no algorithm that is expressible in fixed-point logic with counting (FPC) can compute an approximate solution. Since important algorithmic techniques for approximation algorithms (such as linear or semidefinite programming) are expressible in FPC, this yields lower bounds on what can be achieved by such methods. The results are established by showing lower bounds on the number of variables required in first-order logic with counting to separate instances with a high optimum from those with a low optimum for fixed-size instances., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

On the power of symmetric linear programs

  • Atserias, Albert
  • Dawar, Anuj
  • Ochremiak, Joanna
© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991) showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

A parameterized halting problem, the linear time hierarchy, and the MRDP theorem

  • Chen, Yijia
  • Muller, Moritz Martin
  • Yokoyama, Keita
The complexity of the parameterized halting problem for nondeterministic Turing machines p-Halt is known to be related to the question of whether there are logics capturing various complexity classes [10]. Among others, if p-Halt is in para-AC0, the parameterized version of the circuit complexity class AC0, then AC0, or equivalently, (+, x)-invariant FO, has a logic. Although it is widely believed that p-Halt ∉. para-AC0, we show that the problem is hard to settle by establishing a connection to the question in classical complexity of whether NE ⊈ LINH. Here, LINH denotes the linear time hierarchy. On the other hand, we suggest an approach toward proving NE ⊈ LINH using bounded arithmetic. More specifically, we demonstrate that if the much celebrated MRDP (for Matiyasevich-Robinson-Davis-Putnam) theorem can be proved in a certain fragment of arithmetic, then NE ⊈ LINH. Interestingly, central to this result is a para-AC0 lower bound for the parameterized model-checking problem for FO on arithmetical structures., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Proving termination through conditional termination

  • Borralleras Andreu, Cristina
  • Brockschmidt, Marc
  • Larraz Hurtado, Daniel
  • Oliveras Llunell, Albert
  • Rodríguez Carbonell, Enric
  • Rubio Gimeno, Alberto
We present a constraint-based method for proving conditional termination of integer programs. Building on this, we construct a framework to prove (unconditional) program termination using a powerful mechanism to combine conditional termination proofs. Our key insight is that a conditional termination proof shows termination for a subset of program execution states which do not need to be considered in the remaining analysis. This facilitates more effective termination as well as non-termination analyses, and allows handling loops with different execution phases naturally. Moreover, our method can deal with sequences of loops compositionally. In an empirical evaluation, we show that our implementation VeryMax outperforms state-of-the-art tools on a range of standard benchmarks., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Circular (yet sound) proofs

  • Atserias, Albert
  • Lauria, Massimo
We introduce a new way of composing proofs in rule-based proof systems that generalizes tree-like and dag-like proofs. In the new definition, proofs are directed graphs of derived formulas, in which cycles are allowed as long as every formula is derived at least as many times as it is required as a premise. We call such proofs circular. We show that, for all sets of standard inference rules, circular proofs are sound. We first focus on the circular version of Resolution, and see that it is stronger than Resolution since, as we show, the pigeonhole principle has circular Resolution proofs of polynomial size. Surprisingly, as proof systems for deriving clauses from clauses, Circular Resolution turns out to be equivalent to Sherali-Adams, a proof system for reasoning through polynomial inequalities that has linear programming at its base. As corollaries we get: (1) polynomial-time (LP-based) algorithms that find circular Resolution proofs of constant width, (2) examples that separate circular from dag-like Resolution, such as the pigeonhole principle and its variants, and (3) exponentially hard cases for circular Resolution. Contrary to the case of circular resolution, for Frege we show that circular proofs can be converted into tree-like ones with at most polynomial overhead., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Caterpillars are antimagic

  • Lozano Boixadors, Antoni
  • Mora Giné, Mercè
  • Seara Ojea, Carlos
  • Tey Carrera, Joaquín
An antimagic labeling of a graph G is a bijection from the set of edges E(G) to {1,2,…,|E(G)|}, such that all vertex sums are pairwise distinct, where the vertex sum at vertex u is the sum of the labels assigned to the edges incident to u. A graph is called antimagic when it has an antimagic labeling. Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic and the conjecture remains open even for trees. Here, we prove that caterpillars are antimagic by means of an O(nlogn) algorithm., Antoni Lozano is 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). Mercè Mora is supported by projects Gen. Cat. DGR 2017SGR1336, MINECO MTM2015-63791-R, and H2020-MSCA-RISE project 734922-CONNECT. Carlos Seara is supported by projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and H2020-MSCA-RISE project 734922-CONNECT. Joaquin Tey is supported by project PRODEP-12612731., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Non-homogenizable classes of finite structures

  • Atserias, Albert
  • Torunczyk, Szymon Abram
Homogenization is a powerful way of taming a class of finite structures with several interesting applications in different areas, from Ramsey theory in combinatorics to constraint satisfaction problems (CSPs) in computer science, through (finite) model theory. A few sufficient conditions for a class of finite structures to allow homogenization are known, and here we provide a necessary condition. This lets us show that certain natural classes are not homogenizable: 1) the class of locally consistent systems of linear equations over the two-element field or any finite Abelian group, and 2) the class of finite structures that forbid homomorphisms from a specific MSO-definable class of structures of treewidth two. In combination with known results, the first example shows that, up to pp-interpretability, the CSPs that are solvable by local consistency methods are distinguished from the rest by the fact that their classes of locally consistent instances are homogenizable. The second example shows that, for MSO-definable classes of forbidden patterns, treewidth one versus two is the dividing line to homogenizability., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Antimagic labelings of caterpillars

  • Lozano Boixadors, Antoni
  • Mora Giné, Mercè
  • Seara Ojea, Carlos
A k-antimagic labeling of a graph G is an injection from E(G) to {1,2, ..., |E(G)|+k} such that all vertex sums are pairwise distinct, where the vertex sum at vertex u is the sum of the labels assigned to edges incident to u. We call a graph k-antimagic when it has a k-antimagic labeling, and antimagic when it is 0-antimagic. Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic, but the conjecture is still open even for trees. Here we study k-antimagic labelings of caterpillars. We use algorithmic and constructive techniques, instead of the standard Combinatorial NullStellenSatz method, to prove our results: (i) any caterpillar of order n is (⌊(n−1)/2⌋−2)-antimagic; (ii) any caterpillar with a spine of order s with either at least ⌊(3s+1)/2⌋ leaves or ⌊(s−1)/2⌋ consecutive vertices of degree at most 2 at one end of a longest path, is antimagic; and (iii) if p is a prime number, any caterpillar with a spine of order p, p−1 or p−2 is 1-antimagic., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Feasibly constructive proofs of succinct weak circuit lower bounds

  • Muller, Moritz Martin
  • Pich, Ján
We ask for feasibly constructive proofs of known circuit lower bounds for explicit functions on bit strings of length n. In 1995 Razborov showed that many can be proved in PV1, a bounded arithmetic formalizing polynomial time reasoning. He formalized circuit lower bound statements for small n of doubly logarithmic order. It is open whether PV1 proves known lower bounds in succinct formalizations for n of logarithmic order. We give such proofs in APC1, an extension of PV1 formalizing probabilistic polynomial time reasoning: for parity and AC0, for mod q and AC0[p] (only for n slightly smaller than logarithmic), and for k-clique and monotone circuits. We also formalize Razborov and Rudich’s natural proof barrier. We ask for short propositional proofs of circuit lower bounds expressed succinctly by propositional formulas of size nO(1) or at least much smaller than the 2O(n) size of the common “truth table” formula. We discuss two such expressions: one via feasible functions witnessing errors of circuits, and one via the anticheckers of Lipton and Young 1994. Our APC1 formalizations yield conditional upper bounds for the succinct formulas obtained by witnessing: we get short Extended Frege proofs from general circuit lower bounds expressed by the common “truth-table” formulas. We also show how to construct in quasipolynomial time propositional proofs of quasipolynomial size tautologies expressing AC0[p] quasipolynomial size lower bounds; these proofs are in Jerábek’s system WF., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Relative entailment among probabilistic implications

  • Atserias, Albert
  • Balcázar Navarro, José Luis
  • Piceno Cabrera, Marie Ely
We study a natural variant of the implicational fragment of propositional logic. Its formulas are pairs of conjunctions of positive literals, related together by an implicational-like connective; the semantics of this sort of implication is defined in terms of a threshold on a conditional probability of the consequent, given the antecedent: we are dealing with what the data analysis community calls confidence of partial implications or association rules. Existing studies of redundancy among these partial implications have characterized so far only entailment from one premise and entailment from two premises, both in the stand-alone case and in the case of presence of additional classical implications (this is what we call "relative entailment"). By exploiting a previously noted alternative view of the entailment in terms of linear programming duality, we characterize exactly the cases of entailment from arbitrary numbers of premises, again both in the stand-alone case and in the case of presence of additional classical implications. As a result, we obtain decision algorithms of better complexity; additionally, for each potential case of entailment, we identify a critical confidence threshold and show that it is, actually, intrinsic to each set of premises and antecedent of the conclusion., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Proof complexity meets algebra

  • Atserias, Albert
  • Ochremiak, Joanna
We analyze how the standard reductions between constraint satisfaction problems affect their proof complexity. We show that, for the most studied propositional, algebraic, and semialgebraic proof systems, the classical constructions of pp-interpretability, homomorphic equivalence, and addition of constants to a core preserve the proof complexity of the CSP. As a result, for those proof systems, the classes of constraint languages for which small unsatisfiability certificates exist can be characterized algebraically. We illustrate our results by a gap theorem saying that a constraint language either has resolution refutations of constant width or does not have bounded-depth Frege refutations of subexponential size. The former holds exactly for the widely studied class of constraint languages of bounded width. This class is also known to coincide with the class of languages with refutations of sublinear degree in Sums of Squares and Polynomial Calculus over the real field, for which we provide alternative proofs. We then ask for the existence of a natural proof system with good behavior with respect to reductions and simultaneously small-size refutations beyond bounded width. We give an example of such a proof system by showing that bounded-degree Lovász-Schrijver satisfies both requirements. Finally, building on the known lower bounds, we demonstrate the applicability of the method of reducibilities and construct new explicit hard instances of the graph three-coloring problem for all studied proof systems., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A remark on pseudo proof systems and hard instances of the satisfiability problem

  • Maly, Jan
  • Muller, Moritz Martin
We link two concepts from the literature, namely hard sequences for the satisfiability problem sat and so-called pseudo proof systems proposed for study by Krajícek. Pseudo proof systems are elements of a particular nonstandard model constructed by forcing with random variables. We show that the existence of mad pseudo proof systems is equivalent to the existence of a randomized polynomial time procedure with a highly restrictive use of randomness which produces satisfiable formulas whose satisfying assignments are probably hard to find., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Automating resolution is NP-Hard

  • Atserias, Albert
  • Muller, Moritz Martin
We show that the problem of finding a Resolution refutation that is at most polynomially longer than a shortest one is NP-hard. In the parlance of proof complexity, Resolution is not automatable unless P = NP. Indeed, we show that it is NP-hard to distinguish between formulas that have Resolution refutations of polynomial length and those that do not have subexponential length refutations. This also implies that Resolution is not automatable in subexponential time or quasi-polynomial time unless NP is included in SUBEXP or QP, respectively., Both authors were 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). First author partially funded by MICCIN grant TIN2016-76573-C2-1P (TASSAT3)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

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

  • Atserias, Albert
  • Ochremiak, 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 use this observation to 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. © 2018 ACM., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

On the power of symmetric linear programs

  • Atserias, Albert
  • Dawar, Anuj
  • Ochremiak, Joanna Regina
We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs, while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991), showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem., First author 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 MICCIN grant TIN2016-76573-C2-1P (TASSAT3). The second author was partially supported by a Fellowship of the Alan Turing Institute under the EPSRC grant EP/N510129/1. The third author funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 795936., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Some subsystems of constant-depth Frege with parity

  • Garlik, Michal
  • Kolodziejczyk, Andrzej
We consider three relatively strong families of subsystems of AC0[2]-Frege proof systems, i.e., propositional proof systems using constant-depth formulas with an additional parity connective, for which exponential lower bounds on proof size are known. In order of increasing strength, the subsystems are (i) constant-depth proof systems with parity axioms and the (ii) treelike and (iii) daglike versions of systems introduced by Krajíček which we call PKcd(⊕). In a PKcd(⊕)-proof, lines are disjunctions (cedents) in which all disjuncts have depth at most d, parities can only appear as the outermost connectives of disjuncts, and all but c disjuncts contain no parity connective at all. We prove that treelike PKO(1)O(1)(⊕) is quasipolynomially but not polynomially equivalent to constant-depth systems with parity axioms. We also verify that the technique for separating parity axioms from parity connectives due to Impagliazzo and Segerlind can be adapted to give a superpolynomial separation between daglike PKO(1)O(1)(⊕) and AC0[2]-Frege; the technique is inherently unable to prove superquasipolynomial separations. We also study proof systems related to the system Res-Lin introduced by Itsykson and Sokolov. We prove that an extension of treelike Res-Lin is polynomially simulated by a system related to daglike PKO(1)O(1)(⊕), and obtain an exponential lower bound for this system., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication Artículo científico (JournalArticle)

Co-occurrence patterns in diagnostic data

  • Piceno Cabrera, Marie Ely
  • Rodríguez Navas, Laura
  • Balcázar Navarro, José Luis
We demonstrate how graph decomposition techniques can be employed for the visualization of hierarchical co-occurrence patterns between medical data items. Our research is based on Gaifman graphs (a mathematical concept introduced in Logic), on specific variants of this concept, and on existing graph decomposition notions, specifically, graph modules and the clan decomposition of so-called 2-structures. The construction of the Gaifman graphs from a dataset is based on co-occurrence, or lack of it, of items in the dataset. We may select a discretization on the edge labels to aim at one among several Gaifman graph variants. Then, the decomposition of the graph may provide us with visual information about the data co-occurrences, after which one can proceed to more traditional statistical analysis., Partially supported by European Research Council (ERC) under the European Union's Horizon2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR);by grant TIN2017-89244-R from Ministerio de Economia, Industria y Competitividad, and byConacyt (México). We acknowledge unfunded recognition 2017SGR-856 (MACDA) from AGAUR(Generalitat de Catalunya)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Trade-offs between time and memory in a tighter model of CDCL SAT solvers

  • Elffers, J.
  • Johannsen, Jan
  • Lauria, Massimo
  • Magnard, Thomas
  • Nordström, Jakob
  • Vinyals, Marc
"The final publication is available at http://link.springer.com/chapter/10.1007/978-3-319-40970-2_11, A long line of research has studied the power of conflict- driven clause learning (CDCL) and how it compares to the resolution proof system in which it searches for proofs. It has been shown that CDCL can polynomially simulate resolution even with an adversarially chosen learning scheme as long as it is asserting. However, the simulation only works under the assumption that no learned clauses are ever forgot- ten, and the polynomial blow-up is significant. Moreover, the simulation requires very frequent restarts, whereas the power of CDCL with less frequent or entirely without restarts remains poorly understood. With a view towards obtaining results with tighter relations between CDCL and resolution, we introduce a more fine-grained model of CDCL that cap- tures not only time but also memory usage and number of restarts. We show how previously established strong size-space trade-offs for resolution can be transformed into equally strong trade-offs between time and memory usage for CDCL, where the upper bounds hold for CDCL with- out any restarts using the standard 1UIP clause learning scheme, and the (in some cases tightly matching) lower bounds hold for arbitrarily frequent restarts and arbitrary clause learning schemes., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Definable inapproximability: New challenges for duplicator

  • Atserias, Albert
  • Dawar, Anuj
We consider the hardness of approximation of optimization problems from the point of view of definability. For many NP-hard optimization problems it is known that, unless P = NP, no polynomial-time algorithm can give an approximate solution guaranteed to be within a fixed constant factor of the optimum. We show, in several such instances and without any complexity theoretic assumption, that no algorithm that is expressible in fixed-point logic with counting (FPC) can compute an approximate solution. Since important algorithmic techniques for approximation algorithms (such as linear or semidefinite programming) are expressible in FPC, this yields lower bounds on what can be achieved by such methods. The results are established by showing lower bounds on the number of variables required in first-order logic with counting to separate instances with a high optimum from those with a low optimum for fixed-size instances., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Incomplete SMT techniques for solving non-linear formulas over the integers

  • Borralleras Andreu, Cristina
  • Larraz Hurtado, Daniel
  • Rodríguez Carbonell, Enric
  • Oliveras Llunell, Albert
  • Rubio Gimeno, Alberto
We present new methods for solving the Satisfiability Modulo Theories problem over the theory of QuantifierFree Non-linear Integer Arithmetic, SMT(QF-NIA), which consists of deciding the satisfiability of ground formulas with integer polynomial constraints. Following previous work, we propose to solve SMT(QF-NIA) instances by reducing them to linear arithmetic: non-linear monomials are linearized by abstracting them with fresh variables and by performing case splitting on integer variables with finite domain. For variables that do not have a finite domain, we can artificially introduce one by imposing a lower and an upper bound and iteratively enlarge it until a solution is found (or the procedure times out). The key for the success of the approach is to determine, at each iteration, which domains have to be enlarged. Previously, unsatisfiable cores were used to identify the domains to be changed, but no clue was obtained as to how large the new domains should be. Here, we explain two novel ways to guide this process by analyzing solutions to optimization problems: (i) to minimize the number of violated artificial domain bounds, solved via a Max-SMT solver, and (ii) to minimize the distance with respect to the artificial domains, solved via an Optimization Modulo Theories (OMT) solver. Using this SMT-based optimization technology allows smoothly extending the method to also solve Max-SMT problems over non-linear integer arithmetic. Finally, we leverage the resulting Max-SMT(QF-NIA) techniques to solve ∃∀ formulas in a fragment of quantified non-linear arithmetic that appears commonly in verification and synthesis applications., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Trees whose even-degree vertices induce a path are antimagic

  • Lozano Boixadors, Antoni
  • Mora Giné, Mercè
  • Seara Ojea, Carlos
  • Tey Carrera, Joaquín
An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . . , |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic; however the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Anti-magic labeling of trees, Discrete Math. 331 (2014) 9–14]., A. Lozano is 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); M. Mora is supported by projects Gen. Cat. DGR 2017SGR1336, MINECO MTM2015-63791-R, and H2020-MSCARISE project 734922-CONNECT; and C. Seara is supported by projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and H2020-MSCARISE project 734922-CONNECT., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication

Trees whose even-degree vertices induce a path are antimagic

  • Lozano Boixadors, Antoni
  • Mora Giné, Mercè
  • Seara Ojea, Carlos
  • Tey Carrera, Joaquín
An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . . , |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic; however, the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Discrete Math. 331 (2014) 9–14]., Preprint
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Feasible interpolation for polynomial calculus and sums-of-squares

  • Hakoniemi, Tuomas Antero
We prove that both Polynomial Calculus and Sums-of-Squares proof systems admit a strong form of feasible interpolation property for sets of polynomial equality constraints. Precisely, given two sets P(x, z) and Q(y, z) of equality constraints, a refutation Π of P(x, z) ∪ Q(y, z), and any assignment a to the variables z, one can find a refutation of P(x, a) or a refutation of Q(y, a) in time polynomial in the length of the bit-string encoding the refutation Π. For Sums-of-Squares we rely on the use of Boolean axioms, but for Polynomial Calculus we do not assume their presence., 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 MICCIN grant TIN2016-76573-C2-1P (TASSAT3)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Clique is hard on average for regular resolution

  • Atserias, Albert
  • Bonacina, Ilario
  • Rezende, Susanna F. de
  • Lauria, Massimo
  • Nordström, Jakob
  • Razborov, Alexander
We prove that for k ≪4√n regular resolution requires length nΩ(k) to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional nΩ(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

The parameterized space complexity of model-checking bounded variable first-order logic

  • Chen, Yijia
  • Elberfeld, Michael
  • Muller, Moritz Martin
The parameterized model-checking problem for a class of first-order sentences (queries) asks to decide whether a given sentence from the class holds true in a given relational structure (database); the parameter is the length of the sentence. We study the parameterized space complexity of the model-checking problem for queries with a bounded number of variables. For each bound on the quantifier alternation rank the problem becomes complete for the corresponding level of what we call the tree hierarchy, a hierarchy of parameterized complexity classes defined via space bounded alternating machines between parameterized logarithmic space and fixed-parameter tractable time. We observe that a parameterized logarithmic space model-checker for existential bounded variable queries would allow to improve Savitch's classical simulation of nondeterministic logarithmic space in deterministic space O(log2n). Further, we define a highly space efficient model-checker for queries with a bounded number of variables and bounded quantifier alternation rank. We study its optimality under the assumption that Savitch's Theorem is optimal., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Homomorphism problems for first-order definable structures

  • Klin, Bartek
  • Lasota, Slawomir
  • Ochremiak, Joanna Regina
  • Torunczyk, Szymon Abram
We investigate several variants of the homomorphism problem: given two relational structures, is there a homomorphism from one to the other? The input structures are possibly infinite, but definable by first-order interpretations in a fixed structure. Their signatures can be either finite or infinite but definable. The homomorphisms can be either arbitrary, or definable with parameters, or definable without parameters. For each of these variants, we determine its decidability status., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Polynomial time ultrapowers and the consistency of circuit lower bounds

  • Bydžovský, Jan
  • Muller, Moritz Martin
A polynomial time ultrapower is a structure given by the set of polynomial time computable functions modulo some ultrafilter. They model the universal theory ∀PV of all polynomial time functions. Generalizing a theorem of Hirschfeld (Israel J Math 20(2):111–126, 1975), we show that every countable model of ∀PV is isomorphic to an existentially closed substructure of a polynomial time ultrapower. Moreover, one can take a substructure of a special form, namely a limit polynomial time ultrapower in the classical sense of Keisler (in: Bergelson, V., Blass, A., Di Nasso, M., Jin, R. (eds.) Ultrafilters across mathematics, contemporary mathematics vol 530, pp 163–179. AMS, New York, 1963). Using a polynomial time ultrapower over a nonstandard Herbrand saturated model of ∀PV we show that ∀PV is consistent with a formal statement of a polynomial size circuit lower bound for a polynomial time computable function. This improves upon a recent result of Krajíček and Oliveira (Logical methods in computer science 13 (1:4), 2017)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Distinguishing tournaments with small label classes

  • Lozano Boixadors, Antoni
A d-distinguishing vertex (arc) labeling of a digraph is a vertex (arc) labeling using d labels that is not preserved by any nontrivial automorphism. Let ρ(T) (ρ′(T)) be the minimum size of a label class in a 2-distinguishing vertex (arc) labeling of a tournament T. Gluck's Theorem implies that ρ(T) ≤ ⌊n/2⌋ for any tournament T of order n. We construct a family of tournaments ℌ such that ρ(T) ≥ ⌊n/2⌋ for any tournament of order n in ℌ. Additionally, we prove that ρ′(T) ≤ ⌊7n/36⌋ + 3 for any tournament T of order n and ρ′(T) ≥ ⌈n/6⌉ when T ∈ ℌ and has order n. These results answer some open questions stated by Boutin., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Circular (yet sound) proofs in propositional logic

  • Atserias, Albert
  • Lauria, Massimo
Proofs in propositional logic are typically presented as trees of derived formulas or, alternatively, as directed acyclic graphs of derived formulas. This distinction between tree-like vs. dag-like structure is particularly relevant when making quantitative considerations regarding, for example, proof size. Here we analyze a more general type of structural restriction for proofs in rule-based proof systems. In this definition, proofs are directed graphs of derived formulas in which cycles are allowed as long as every formula is derived at least as many times as it is required as a premise. We call such proofs “circular”. We show that, for all sets of standard inference rules with single or multiple conclusions, circular proofs are sound. We start the study of the proof complexity of circular proofs at Circular Resolution, the circular version of Resolution. We immediately see that Circular Resolution is stronger than dag-like Resolution since, as we show, the propositional encoding of the pigeonhole principle has circular Resolution proofs of polynomial size. Furthermore, for derivations of clauses from clauses, we show that Circular Resolution is, surprisingly, equivalent to Sherali-Adams, a proof system for reasoning through polynomial inequalities that has linear programming at its base. As corollaries we get: (1) polynomial-time (LP-based) algorithms that find Circular Resolution proofs of constant width, (2) examples that separate Circular from dag-like Resolution, such as the pigeonhole principle and its variants, and (3) exponentially hard cases for Circular Resolution. Contrary to the case of Circular Resolution, for Frege we show that circular proofs can be converted into tree-like proofs with at most polynomial overhead., Albert Atserias and Massimo Lauria were 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). Albert Atserias partially funded by MINECO through TIN2013-48031-C4-1-P (TASSAT2)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Generalized satisfiability problems via operator assignments

  • Atserias, Albert
  • Kolaitis, Phokion
  • Severini, Simone
Schaefer introduced a framework for generalized satisfiability problems on the Boolean domain and characterized the computational complexity of such problems. We investigate an algebraization of Schaefer's framework in which the Fourier transform is used to represent constraints by multilinear polynomials in a unique way. This representation of constraints gives rise to a relaxation of the notion of satisfiability in which the values to variables are linear operators on some Hilbert space. For constraints given by a system of linear equations over the two-element field, earlier work in the foundations of quantum mechanics has shown that there are systems that have no solutions in the Boolean domain, but have solutions via operator assignments on some finite-dimensional Hilbert space. Our main result is a complete characterization of the classes of Boolean relations for which there is a gap between satisfiability in the Boolean domain and the relaxation of satisfiability via operator assignments., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Probabilities of first-order sentences on sparse random relational structures: An application to definability on random CNF formulas

  • Larrauri Borroto, Lázaro Alberto
We extend the convergence law for sparse random graphs proven by Lynch to arbitrary relational languages. We consider a finite relational vocabulary s and a first-order theory T for s composed of symmetry and anti-reflexivity axioms. We define a binomial random model of finite s-structures that satisfy T and show that first-order properties have well defined asymptotic probabilities when the expected number of tuples satisfying each relation in s is linear. It is also shown that these limit probabilities are well behaved with respect to several parameters that represent the density of tuples in each relation R in the vocabulary s¿. An application of these results to the problem of random Boolean satisfiability is presented. We show that in a random k-CNF formula on n variables, where each possible clause occurs with probability ~c/nk-1¿, independently any first-order property of k-CNF formulas that implies unsatisfiability does almost surely not hold as n tends to infinity., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Resolution lower bounds for refutation statements

  • Garlik, Michal
For any unsatisfiable CNF formula we give an exponential lower bound on the size of resolutionrefutations of a propositional statement that the formula has a resolution refutation. We describethree applications. (1) An open question in [2] asks whether a certain natural propositional encodingof the above statement is hard for Resolution. We answer by giving an exponential size lower bound.(2) We show exponential resolution size lower bounds for reflection principles, thereby improvinga result in [1]. (3) We provide new examples of CNFs that exponentially separate Res(2) fromResolution (an exponential separation of these two proof systems was originally proved in [10])., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Quantum and non-signalling graph isomorphisms

  • Atserias, Albert
  • Mancinska, Laura
  • Roberson, David E.
  • Samal, Robert
  • Severini, Simone
  • Varvitsiotis, Antonios
We introduce the (G,H)-isomorphism game, a new two-player non-local game that classical players can win with certainty iff the graphs G and H are isomorphic. We then define quantum and non-signalling isomorphisms by considering perfect quantum and non-signalling strategies for this game. We prove that non-signalling isomorphism coincides with fractional isomorphism, giving the latter an operational interpretation. We show that quantum isomorphism is equivalent to the feasibility of two polynomial systems obtained by relaxing standard integer programs for graph isomorphism to Hermitian variables. Finally, we provide a reduction from linear binary constraint system games to isomorphism games. This reduction provides examples of quantum isomorphic graphs that are not isomorphic, implies that the tensor product and commuting operator frameworks result in different notions of quantum isomorphism, and proves that both relations are undecidable., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Proof complexity meets algebra

  • Atserias, Albert
  • Ochremiak, Joanna
We analyse how the standard reductions between constraint satisfaction problems affect their proof complexity. We show that, for the most studied propositional and semi-algebraic proof systems, the classical constructions of pp-interpretability, homomorphic equivalence and addition of constants to a core preserve the proof complexity of the CSP. As a result, for those proof systems, the classes of constraint languages for which small unsatisfiability certificates exist can be characterised algebraically. We illustrate our results by a gap theorem saying that a constraint language either has resolution refutations of bounded width, or does not have bounded-depth Frege refutations of subexponential size. The former holds exactly for the widely studied class of constraint languages of bounded width. This class is also known to coincide with the class of languages with Sums-of-Squares refutations of sublinear degree, a fact for which we provide an alternative proof. We hence ask for the existence of a natural proof system with good behaviour with respect to reductions and simultaneously small size refutations beyond bounded width. We give an example of such a proof system by showing that bounded-degree Lovasz-Schrijver satisfies both requirements., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Size-degree trade-offs for Sums-of-Squares and Positivstellensatz proofs

  • Atserias, Albert
  • Hakoniemi, Tuomas Antero
We show that if a system of degree-k polynomial constraints on n Boolean variables has a Sums-of-Squares (SOS) proof of unsatisfiability with at most s many monomials, then it also has one whose degree is of the order of the square root of n log s plus k. A similar statement holds for the more general Positivstellensatz (PS) proofs. This establishes size-degree trade-offs for SOS and PS that match their analogues for weaker proof systems such as Resolution, Polynomial Calculus, and the proof systems for the LP and SDP hierarchies of Lovász and Schrijver. As a corollary to this, and to the known degree lower bounds, we get optimal integrality gaps for exponential size SOS proofs for sparse random instances of the standard NP-hard constraint optimization problems. We also get exponential size SOS lower bounds for Tseitin and Knapsack formulas. The proof of our main result relies on a zero-gap duality theorem for pre-ordered vector spaces that admit an order unit, whose specialization to PS and SOS may be of independent interest., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Automating Resolution is NP-hard

  • Atserias, Albert
  • Muller, Moritz Martin
We show that the problem of finding a Resolution refutation that is at most polynomially longer than a shortest one is NP-hard. In the parlance of proof complexity, Resolution is not automatizable unless P = NP. Indeed, we show that it is NP-hard to distinguish between formulas that have Resolution refutations of polynomial length and those that do not have subexponential length refutations. This also implies that Resolution is not automatizable in subexponential time or quasi-polynomial time unless~NP is included in SUBEXP or QP, respectively., Peer Reviewed, Postprint (author's final draft)