This paper is concerned with the complexity of proofs and of searching for proofs in
resolution. We show that the recently proposed algorithm of Ben-Sasson & Wigderson for …

We prove that the problem of determining the minimum propositional proof length is NP-hard
to approximate within a factor of. These results are very robust in that they hold for almost all …

This paper shows that any sequence \psi_n of tautologies which expresses the validity of a
fixed combinatorial principle either is “easy”, ie has polynomial size tree-resolution proofs, or …

We consider tautologies formed from a pseudo-random number generator, defined in
Krajíček [11] and in Alekhnovich et al.[2]. We explain a strategy of proving their hardness for …

We study the complexity of proving the Pigeon Hole Principle (PHP) in a monotone variant of
the Gentzen Calculus, also known as Geometric Logic. We prove a size‐depth trade‐off …

In this thesis we are concerned with building logical foundations for Linear Algebra, from the
perspective of proof complexity. As the cornerstone of our logical theories, we use …

Regular resolution lower bounds for the weak pigeonhole principle Page 1 Regular
Resolution Lower Bounds for the Weak Pigeonhole Principle Toniann Pitassi * Department …

In this thesis we investigate two closely related notions of simulation between proof systems
that are used to compare proof systems within respect to proof length (simulation) or within …

An important approach to solving many discrete optimization problems is to associate the
discrete set (over which we wish to optimize) with the 0-1 vectors in a given polyhedron and …

This paper presents the TAS methodology1 as a new framework for generating non-clausal
Automated Theorem Provers. We present a complete description of the ATP for Classical …