79 citations · 93 across the 20 of their papers we have counts for
28 papers
From Gödel incompleteness to the consistency of circuit lower bounds
Albert Atserias, Moritz Müller
We prove that the bounded arithmetic theory is consistent with EXP P/poly. More generally, we show that certain separations of from a theory imp…
Hard Clique Formulas for Resolution
Albert Atserias
We show how to convert any unsatisfiable 3-CNF formula which is sparse and exponentially hard to refute in Resolution into a negative instance of the -clique problem whose corre…
Gamma Acyclicity, Annotated Relations, and Consistency Witness Functions
Albert Atserias, Phokion G. Kolaitis
During the early days of relational database theory it was realized that "acyclic" database schemas possess a number of desirable semantic properties. In fact, three different noti…
The Proof Analysis Problem
Noel Arteche, Albert Atserias, Susanna F. de Rezende +1
Atserias and Müller (JACM, 2020) proved that for every unsatisfiable CNF formula , the formula , stating " has small Resolution refutations", does not…
Simple general magnification of circuit lower bounds
Albert Atserias, Moritz Müller
We introduce a technically and conceptually simple approach to magnification of circuit and formula lower bounds. Central to the method are so-called distinguishers, sparse matrice…
Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
Albert Atserias, Iddo Tzameret
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 finit…
Consistency of Relations over Monoids
Albert Atserias, Phokion G. Kolaitis
The interplay between local consistency and global consistency has been the object of study in several different areas, including probability theory, relational databases, and quan…
On the Consistency of Circuit Lower Bounds for Non-Deterministic Time
Albert Atserias, Sam Buss, Moritz Müller
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…
Promise Constraint Satisfaction and Width
Albert Atserias, Víctor Dalmau
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 tha…
On the Expressive Power of Homomorphism Counts
Albert Atserias, Phokion G. Kolaitis, Wei-Lin Wu
A classical result by Lovász asserts that two graphs and are isomorphic if and only if they have the same left profile, that is, for every graph , the number of homomorp…
Structure and Complexity of Bag Consistency
Albert Atserias, Phokion G. Kolaitis
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-n…
Clique Is Hard on Average for Regular Resolution
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende +3
We prove that for regular resolution requires length to establish that an Erdős-Rényi graph with appropriately chosen edge density does not contain a…
Consistency, Acyclicity, and Positive Semirings
Albert Atserias, Phokion G. Kolaitis
In several different settings, one comes across situations in which the objects of study are locally consistent but globally inconsistent. Earlier work about probability distributi…
Automating Resolution is NP-Hard
Albert Atserias, Moritz Müller
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 n…
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…
Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs
Albert Atserias, Tuomas Hakoniemi
We show that if a system of degree- polynomial constraints on~ Boolean variables has a Sums-of-Squares (SOS) proof of unsatisfiability with at most~ many monomials, then i…
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.…
Size bounds and query plans for relational joins
Albert Atserias, Martin Grohe, Dániel Marx
Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often domin…
Proof Complexity Meets Algebra
Albert Atserias, Joanna Ochremiak
We analyse how the standard reductions between constraint satisfaction problems affect their proof complexity. We show that, for the most studied propositional, algebraic, and semi…
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…
Quantum and non-signalling graph isomorphisms
Albert Atserias, Laura Mančinska, David E. Roberson +3
We introduce a two-player nonlocal game, called the -isomorphism game, where classical players can win with certainty if and only if the graphs and are isomorphic. W…
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…