3 papers
cs.CC2021
Monomial-size vs. Bit-complexity in Sums-of-Squares and Polynomial Calculus
Tuomas Hakoniemi
In this paper we consider the relationship between monomial-size and bit-complexity in Sums-of-Squares (SOS) in Polynomial Calculus Resolution over rationals (PCR/). We…
cs.CC2018
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…
math.LO2016
Labelled tableaux for interpretability logics
Tuomas A. Hakoniemi, Joost J. Joosten
In is paper we present a labelled tableau proof system that serves a wide class of interpretability logics. The system is proved sound and complete for any interpretability logic c…