Complexity of Semialgebraic Proofs with Restricted Degree of Falsity 1 2

The degree of falsity of an inequality in Boolean variables shows how many variables are enough to substitute in order to satisfy the inequality. Goerdt introduced a weakened version of the Cutting Plane (CP) proof system with a restriction on the degree of falsity of intermediate inequalities [6]. He proved an exponential lower bound for CP proofs with degree of falsity bounded by n log 2 n + 1 , where n is the number of variables.

In this paper we strengthen this result by establishing a direct connection between CP and Resolution proofs. This result implies an exponential lower bound on the proof length of Tseitin-Urquhart tautologies when the degree of falsity is bounded by c n for some constant c. We also generalize the notion of degree of falsity for extensions of Lovász-Schrijver calculi (LS), namely for LS k + CP k proof systems introduced by Grigoriev et al. [8]. We show that any LS k + CP k proof with bounded degree of falsity can be transformed into a Res ( k ) proof. We also prove lower and upper bounds on the proof length of tautologies in LS k + CP k with bounded degree of falsity.