79 citations · 93 across the 20 of their papers we have counts for
Showing 2019Show all
2 papers · 1 filter
cs.CC2019
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…
cs.LO2019
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…