1 citations · 1 across the 5 of their papers we have counts for
6 papers
Hard CNF Instances for Ideal Proof Systems
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Since the introduction of the Ideal Proof System (IPS) by Grochow and Pitassi (J. ACM 2018), a substantial body of work has established size lower bounds for IPS and its fragments.…
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi [GP18]) offer a general model for deriving polynomials in an ideal and refuting unsatisfiable propos…
Simple Hard Instances for Low-Depth Algebraic Proofs
Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret
We prove super-polynomial lower bounds on the size of propositional proof systems operating with constant-depth algebraic circuits over fields of zero characteristic. Specifically,…
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…
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…
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…