Relative Entailment Among Probabilistic Implications

Autor: Albert Atserias, José L. Balcázar, Marie Ely Piceno

Publikováno v: Logical Methods in Computer Science, Vol Volume 15, Issue 1 (2019)

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 i

Externí odkaz: https://doaj.org/article/56a64f91e1ad49488933377e9c8d0e0e

On the power of symmetric linear programs

Autor: Anuj Dawar, Joanna Ochremiak, Albert Atserias

Publikováno v: Recercat. Dipósit de la Recerca de Catalunya
instname
2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Jun 2019, Vancouver, Canada. pp.1-13, ⟨10.1109/LICS.2019.8785792⟩
LICS
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)

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 correspon

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::746f4967e59efa125e18ded72e4757f5
https://hdl.handle.net/2117/384806

On the expressive power of homomorphism counts

Autor: Albert Atserias, Phokion G. Kolaitis, Wei-Lin Wu

Publikováno v: UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
LICS

A classical result by Lov\'asz asserts that two graphs $G$ and $H$ are isomorphic if and only if they have the same left profile, that is, for every graph $F$, the number of homomorphisms from $F$ to $G$ coincides with the number of homomorphisms fro

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4c9e3e05512f6027eed5f81c3ea509aa
https://hdl.handle.net/2117/359548

Clique Is Hard on Average for Regular Resolution

Autor: Susanna F. de Rezende, Ilario Bonacina, Jakob Nordström, Massimo Lauria, Albert Atserias, Alexander A. Razborov

Publikováno v: UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Scopus-Elsevier
Recercat. Dipósit de la Recerca de Catalunya
instname
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
STOC
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing-STOC 2018

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 th

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4358b5424aed31f07e64de86ce6bc749
http://arxiv.org/abs/2012.09476

Quantum and non-signalling graph isomorphisms

Autor: Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, Albert Atserias, Antonios Varvitsiotis

Publikováno v: Journal of Combinatorial Theory, Series B
Atserias, A, Mančinska, L, Roberson, D E, Šámal, R, Severini, S & Varvitsiotis, A 2019, ' Quantum and non-signalling graph isomorphisms ', Journal of Combinatorial Theory. Series B, vol. 136, pp. 289-328 . https://doi.org/10.1016/j.jctb.2018.11.002
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Recercat. Dipósit de la Recerca de Catalunya
instname

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 no

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0f0f65a4e5f897220e549afc0ff4c5b9