BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Albert Atserias

Albert Atserias appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational ComplexityLogic in Computer ScienceArtificial IntelligenceDatabasesDiscrete Mathematics

Catalog footprint

What is connected

5works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2020arXiv

Consistency, Acyclicity, and Positive Semirings

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, Maier, Yannakakis (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, 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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Note on Semi-Algebraic Proofs and Gaussian Elimination over Prime Fields

In this note we show that unsatisfiable systems of linear equations with a constant number of variables per equation over prime finite fields have polynomial-size constant-degree semi-algebraic proofs of unsatisfiability. These are proofs that manipulate polynomial inequalities over the reals with variables ranging in $\{0,1\}$. This upper bound is to be put in contrast with the known fact that, for certain explicit systems of linear equations over the two-element field, such refutations require linear degree and exponential size if they are restricted to so-called static semi-algebraic proofs, and even tree-like semi-algebraic and sums-of-squares proofs. Our upper bound is a more or less direct translation of an argument due to Grigoriev, Hirsch and Pasechnik (Moscow Mathematical Journal, 2002) who did it for a family of linear systems of interest in propositional proof complexity. We point out that their method is more general and can be thought of as simulating Gaussian elimination.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution

We offer a new understanding of some aspects of practical SAT-solvers that are based on DPLL with unit-clause propagation, clause-learning, and restarts. We do so by analyzing a concrete algorithm which we claim is faithful to what practical solvers do. In particular, before making any new decision or restart, the solver repeatedly applies the unit-resolution rule until saturation, and leaves no component to the mercy of non-determinism except for some internal randomness. We prove the perhaps surprising fact that, although the solver is not explicitly designed for it, with high probability it ends up behaving as width-k resolution after no more than O(n^2k+2) conflicts and restarts, where n is the number of variables. In other words, width-k resolution can be thought of as O(n^2k+2) restarts of the unit-resolution rule with learning.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Narrow Proofs May Be Maximally Long

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 (PCR) and Sherali-Adams, implying that the corresponding size upper bounds in terms of degree and rank are tight as well. Our results do not extend all the way to Lasserre, however, where the formulas we study have proofs of constant rank and size polynomial in both n and w.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the dynamic width of the 3-colorability problem

A graph $G$ is 3-colorable if and only if it maps homomorphically to the complete 3-vertex graph $K_3$. The last condition can be checked by a $k$-consistency algorithm where the parameter $k$ has to be chosen large enough, dependent on $G$. Let $W(G)$ denote the minimum $k$ sufficient for this purpose. For a non-3-colorable graph $G$, $W(G)$ is equal to the minimum $k$ such that $G$ can be distinguished from $K_3$ in the $k$-variable existential-positive first-order logic. We define the dynamic width of the 3-colorability problem as the function $W(n)=\max_G W(G)$, where the maximum is taken over all non-3-colorable $G$ with $n$ vertices. The assumption $\mathrm{NP}\ne\mathrm{P}$ implies that $W(n)$ is unbounded. Indeed, a lower bound $W(n)=Ω(\log\log n/\log\log\log n)$ follows unconditionally from the work of Nesetril and Zhu on bounded treewidth duality. The Exponential Time Hypothesis implies a much stronger bound $W(n)=Ω(n/\log n)$ and indeed we unconditionally prove that $W(n)=Ω(n)$. In fact, an even stronger statement is true: A first-order sentence distinguishing any 3-colorable graph on $n$ vertices from any non-3-colorable graph on $n$ vertices must have $Ω(n)$ variables. On the other hand, we observe that $W(G)\le 3\,α(G)+1$ and $W(G)\le n-α(G)+1$ for every non-3-colorable graph $G$ with $n$ vertices, where $α(G)$ denotes the independence number of $G$. This implies that $W(n)\le\frac34\,n+1$, improving on the trivial upper bound $W(n)\le n$. We also show that $W(G)>\frac1{16}\, g(G)$ for every non-3-colorable graph $G$, where $g(G)$ denotes the girth of $G$. Finally, we consider the function $W(n)$ over planar graphs and prove that $W(n)=Θ(\sqrt n)$ in the case.

0 citations0 reviewsNo code linkedOpen access