1. Ran Raz & Iddo Tzameret (2008). Resolution Over Linear Equations and Multilinear Proofs. Annals of Pure and Applied Logic 155 (3):194-224.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  2. Maria Bonet, Toniann Pitassi & Ran Raz (1997). Lower Bounds for Cutting Planes Proofs with Small Coefficients. Journal of Symbolic Logic 62 (3):708-728.
    We consider small-weight Cutting Planes (CP * ) proofs; that is, Cutting Planes (CP) proofs with coefficients up to $\operatorname{Poly}(n)$ . We use the well known lower bounds for monotone complexity to prove an exponential lower bound for the length of CP * proofs, for a family of tautologies based on the clique function. Because Resolution is a special case of small-weight CP, our method also gives a new and simpler exponential lower bound for Resolution. We also prove the following (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation