
Promise Constraint Satisfaction and Width
We study the power of the boundedwidth consistency algorithm in the con...
read it

On the Expressive Power of Homomorphism Counts
A classical result by Lovász asserts that two graphs G and H are isomorp...
read it

Structure and Complexity of Bag Consistency
Since the early days of relational databases, it was realized that acycl...
read it

Clique Is Hard on Average for Regular Resolution
We prove that for k ≪√(n) regular resolution requires length n^Ω(k) to e...
read it

Consistency, Acyclicity, and Positive Semirings
In several different settings, one comes across situations in which the ...
read it

Automating Resolution is NPHard
We show that the problem of finding a Resolution refutation that is at m...
read it

On the Power of Symmetric Linear Programs
We consider families of symmetric linear programs (LPs) that decide a pr...
read it

SizeDegree TradeOffs for SumsofSquares and Positivstellensatz Proofs
We show that if a system of degreek polynomial inequalities on n Boolea...
read it

Definable Inapproximability: New Challenges for Duplicator
We consider the hardness of approximation of optimization problems from ...
read it

Circular (Yet Sound) Proofs
We introduce a new way of composing proofs in rulebased proof systems t...
read it

Definable Ellipsoid Method, SumsofSquares Proofs, and the Isomorphism Problem
The ellipsoid method is an algorithm that solves the (weak) feasibility ...
read it

Proof Complexity Meets Algebra
We analyse how the standard reductions between constraint satisfaction p...
read it

Size bounds and query plans for relational joins
Relational joins are at the core of relational algebra, which in turn is...
read it

ClauseLearning Algorithms with Many Restarts and BoundedWidth Resolution
We offer a new understanding of some aspects of practical SATsolvers th...
read it
Albert Atserias
is this you? claim profile