Pasar al contenido principal

Resultados relacionados

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

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

Towards a characterization of constant-factor approximable Min CSPs

  • Dalmau, Víctor
  • Krokhin, Andrei
  • Manokaran, Rajsekar
Comunicació presentada al Twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, celebrat els dies 4 a 6 de gener de 2015 a San Diego, Califòrnia., We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language Γ on an arbitrary finite domain. The goal in such a problem is to minimize the number of unsatisfied constraints in a given instance of CSP(Γ). A recent result of Ene et al. says that, under the mild technical condition that Γ contains the equality relation, the basic LP relaxation is optimal for constant-factor approximation for Min CSP(Γ) unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we introduce a new natural algebraic condition, stable probability distributions on symmetric polymorphisms of a constraint language, and show that the presence of such distributions on polymorphisms of each arity is necessary and sufficient for the finiteness of the integrality gap for the basic LP relaxation of Min CSP(Γ). We also show how stable distributions on symmetric polymorphisms can in principle be used to round solutions of the basic LP relaxation, and how, for several examples that cover all previously known cases, this leads to efficient constant-factor approximation algorithms for Min CSP(Γ). Finally, we show that the absence of another condition, which is implied by stable distributions, leads to NP-hardness of constant-factor approximation., The first two authors are supported by UK EPSRC grant EP/J000078/01. The first author is also supported by MICCIN grant TIN2013-48031-C4-1.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Short proofs of the Kneser-Lovász coloring principle

  • Aisenberg, James
  • Bonet Carbonell, M. Luisa|||0000-0003-1646-7177
  • Buss, Sam
  • Craciun, Adrian
  • Istrate, Gabriel
We prove that propositional translations of the Kneser–Lovász theorem have polynomial size extended Frege proofs and quasi-polynomial size Frege proofs for all fixed values of k. We present a new counting-based combinatorial proof of the K neser–Lovász theorem based on the Hilton–Milner theorem; this avoids the topological arguments of prior proofs for all but finitely many base cases. We introduce new “truncated Tucker lemma” principles, which are miniaturizations of the octahedral Tucker lemma. The truncated Tucker lemma implies the Kneser–Lovász theorem. We show that the k=1 case of the truncated Tucker lemma has polynomial size extended Frege proofs., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación 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
Publicación Artículo científico (JournalArticle)

Narrow proofs may be maximally long

  • Atserias, Albert|||0000-0002-3732-1989
  • Lauria, Massimo
  • Nordström, Jakob
We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n(Omega(w)). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n(O(w)) is essentially tight. Moreover, our lower bound generalizes to polynomial calculus resolution and Sherali-Adams, implying that the corresponding size upper bounds in terms of degree and rank are tight as well. The lower bound does not extend all the way to Lasserre, however, since we show that there the formulas we study have proofs of constant rank and size polynomial in both n and w., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación 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
Publicación 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
Publicación Artículo científico (JournalArticle)

2-D Tucker is PPA complete

  • Aisenberg, James
  • Bonet Carbonell, M. Luisa|||0000-0003-1646-7177
  • Buss, Sam
The 2-D Tucker search problem is shown to be PPA-hard under many-one reductions; therefore it is complete for PPA. The same holds for k-D Tucker for all k≥2. This corrects a claim in the literature that the Tucker search problem is in PPAD., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación 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
Publicación 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
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Short proofs of the Kneser-Lovász coloring principle

  • Aisenberg, James
  • Bonet Carbonell, M. Luisa
  • Buss, Sam
  • Craciun, Adrian
  • Istrate, Gabriel
We prove that propositional translations of the Kneser–Lovász theorem have polynomial size extended Frege proofs and quasi-polynomial size Frege proofs for all fixed values of k. We present a new counting-based combinatorial proof of the K neser–Lovász theorem based on the Hilton–Milner theorem; this avoids the topological arguments of prior proofs for all but finitely many base cases. We introduce new “truncated Tucker lemma” principles, which are miniaturizations of the octahedral Tucker lemma. The truncated Tucker lemma implies the Kneser–Lovász theorem. We show that the k=1 case of the truncated Tucker lemma has polynomial size extended Frege proofs., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación 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
Publicación Artículo científico (JournalArticle)

Narrow proofs may be maximally long

  • Atserias, Albert
  • Lauria, Massimo
  • Nordström, Jakob
We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n(Omega(w)). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n(O(w)) is essentially tight. Moreover, our lower bound generalizes to polynomial calculus resolution and Sherali-Adams, implying that the corresponding size upper bounds in terms of degree and rank are tight as well. The lower bound does not extend all the way to Lasserre, however, since we show that there the formulas we study have proofs of constant rank and size polynomial in both n and w., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

2-D Tucker is PPA complete

  • Aisenberg, James
  • Bonet Carbonell, M. Luisa
  • Buss, Sam
The 2-D Tucker search problem is shown to be PPA-hard under many-one reductions; therefore it is complete for PPA. The same holds for k-D Tucker for all k≥2. This corrects a claim in the literature that the Tucker search problem is in PPAD., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Towards a characterization of constant-factor approximable Min CSPs

  • Dalmau, Víctor
  • Krokhin, Andrei
  • Manokaran, Rajsekar
Comunicació presentada al Twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, celebrat els dies 4 a 6 de gener de 2015 a San Diego, Califòrnia., We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language Γ on an arbitrary finite domain. The goal in such a problem is to minimize the number of unsatisfied constraints in a given instance of CSP(Γ). A recent result of Ene et al. says that, under the mild technical condition that Γ contains the equality relation, the basic LP relaxation is optimal for constant-factor approximation for Min CSP(Γ) unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we introduce a new natural algebraic condition, stable probability distributions on symmetric polymorphisms of a constraint language, and show that the presence of such distributions on polymorphisms of each arity is necessary and sufficient for the finiteness of the integrality gap for the basic LP relaxation of Min CSP(Γ). We also show how stable distributions on symmetric polymorphisms can in principle be used to round solutions of the basic LP relaxation, and how, for several examples that cover all previously known cases, this leads to efficient constant-factor approximation algorithms for Min CSP(Γ). Finally, we show that the absence of another condition, which is implied by stable distributions, leads to NP-hardness of constant-factor approximation., The first two authors are supported by UK EPSRC grant EP/J000078/01. The first author is also supported by MICCIN grant TIN2013-48031-C4-1.
Recercat. Dipósit de la Recerca de Catalunya
Publicación 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
Publicación 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
Publicación 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)