79 citations · 93 across the 20 of their papers we have counts for
8 papers · 1 filter
On the Power of Symmetric Linear Programs
Albert Atserias, Anuj Dawar, Joanna Ochremiak
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…
Definable Inapproximability: New Challenges for Duplicator
Albert Atserias, Anuj Dawar
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, n…
Circular (Yet Sound) Proofs
Albert Atserias, Massimo Lauria
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-…
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
Albert Atserias, Joanna Fijalkow
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.…
Generalized Satisfiability Problems via Operator Assignments
Albert Atserias, Phokion G. Kolaitis, Simone Severini
Schaefer introduced a framework for generalized satisfiability problems on the Boolean domain and characterized the computational complexity of such problems. We investigate an alg…
Non-Homogenizable Classes of Finite Structures
Albert Atserias, Szymon Toruńczyk
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…
Relative Entailment Among Probabilistic Implications
Albert Atserias, José L. Balcázar, Marie Ely Piceno
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-l…
Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
Albert Atserias, Johannes Klaus Fichte, Marc Thurley
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 co…