M Alekhnovich, S Buss, S Moran… - The Journal of Symbolic …, 2001 - cambridge.org
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 …
S Riis - Computational Complexity, 2001 - Springer
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 …
J Krajíček - Bulletin of Symbolic Logic, 2001 - cambridge.org
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 …
T Pitassi, R Raz - Proceedings of the thirty-third annual ACM symposium …, 2001 - dl.acm.org
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 …