79 citations · 93 across the 20 of their papers we have counts for
4 papers · 1 filter
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.…