Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies.

Arist Kojevnikov Dmitry Itsykson

Published in: ICALP (1) (2006)

Keyphrases

lower bound
semidefinite
natural deduction
upper bound
semidefinite programming
proof search
sequent calculus
np hard
theorem prover
theorem proving
objective function
convex relaxation
sufficient conditions
higher dimensional
optimal solution
learning algorithm
inference rules
special case