Zobrazeno 1 - 10
of 163
pro vyhledávání: '"ATSERIAS, ALBERT"'
Autor:
Atserias, Albert, Tzameret, Iddo
The Schwartz-Zippel Lemma states that if a low-degree multivariate polynomial with coefficients in a field is not zero everywhere in the field, then it has few roots on every finite subcube of the field. This fundamental fact about multivariate polyn
Externí odkaz:
http://arxiv.org/abs/2411.07966
Autor:
Atserias, Albert, Kolaitis, Phokion G.
The interplay between local consistency and global consistency has been the object of study in several different areas, including probability theory, relational databases, and quantum information. For relational databases, Beeri, Fagin, Maier, and Ya
Externí odkaz:
http://arxiv.org/abs/2312.02023
We prove the first unconditional consistency result for superpolynomial circuit lower bounds with a relatively strong theory of bounded arithmetic. Namely, we show that the theory V$^0_2$ is consistent with the conjecture that NEXP $\not\subseteq$ P/
Externí odkaz:
http://arxiv.org/abs/2303.01016
Autor:
Atserias, Albert, Dalmau, Víctor
We study the power of the bounded-width consistency algorithm in the context of the fixed-template Promise Constraint Satisfaction Problem (PCSP). Our main technical finding is that the template of every PCSP that is solvable in bounded width satisfi
Externí odkaz:
http://arxiv.org/abs/2107.05886
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:
http://arxiv.org/abs/2101.12733
Autor:
Atserias, Albert, Kolaitis, Phokion G.
Since the early days of relational databases, it was realized that acyclic hypergraphs give rise to database schemas with desirable structural and algorithmic properties. In a by-now classical paper, Beeri, Fagin, Maier, and Yannakakis established se
Externí odkaz:
http://arxiv.org/abs/2012.12126
Autor:
Atserias, Albert, Bonacina, Ilario, de Rezende, Susanna F., Lauria, Massimo, Nordström, Jakob, Razborov, Alexander
We prove that for $k \ll \sqrt[4]{n}$ regular resolution requires length $n^{\Omega(k)}$ to establish that an Erd\H{o}s-R\'enyi graph with appropriately chosen edge density does not contain a $k$-clique. This lower bound is optimal up to the multipli
Externí odkaz:
http://arxiv.org/abs/2012.09476
Autor:
Atserias, Albert, Kolaitis, Phokion G.
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, Fagin, M
Externí odkaz:
http://arxiv.org/abs/2009.09488
Autor:
Atserias, Albert, Müller, Moritz
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 it is NP-hard to disti
Externí odkaz:
http://arxiv.org/abs/1904.02991
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:
http://arxiv.org/abs/1901.07825