Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus

1. Beame, P., Impagliazzo, R., Krajíček, J., Pitassi, T., Pudlák, P.: Lower bounds on Hilbert's Nullstellensatz and propositional proofs. Proceedings of the London Mathematical Society 73(3) (1996) 1–26

   Google Scholar 

2. Beame, P., Riis, S.: More on the relative strength of counting principles. (submitted)

   Google Scholar 

3. Buss, S., Impagliazzo, R., Krajiček, J., Pudlák, P., Razborov, A. A., Sgall, J.: Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Computational Complexity (to appear)

   Google Scholar 

4. Clegg, M, Edmonds, J., Impagliazzo, R.: Using the Groebner basis algorithm to find proofs of unsatisfiability. In: Proceedings of the 28th ACM Symposium on Theory of Computing, ACM (1996) 174–183

   Google Scholar 

5. Krajĩcek, J.: Bounded arithmetic, propositional logic, and complexity theory. Encyclopedia of Mathematics and Its Applications, Vol. 60 Cambridge University Press (1995)

   Google Scholar 

6. Krajićek, J.: A fundamental problem of mathematical logic. Annals of the Kurt Gödel Society, Springer-Verlag, Collegium Logicum, 2 (1995) 56–64

   Google Scholar 

7. Krajićek, J.: On methods for proving lower bounds in propositional logic. In: Logic and Scientific Methods Eds. M. L. Dalla Chiara et al., (Vol. 1 of Proc. of the Tenth International Congress of Logic, Methodology and Philosophy of Science, Florence (August 19–25, 1995)), Synthese Library, 259 Kluwer Academic Publ., Dordrecht (1997) 69–83

   Google Scholar 

8. Krajićek, J.: On the degree of ideal membership proofs from uniform families of polynomials over a finite field. (in preparation)

   Google Scholar 

9. Krajićek, J.,Pudlák, P., Woods, A.: Exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Random Structures and Algorithms 7(1) (1995) 15–39

   Google Scholar 

10. Pitassi, T., Beame, P., and Impagliazzo, R.: Exponential lower bounds for the pigeonhole principle. Computational Complexity 3(2) (1993) 97–140

    Article  Google Scholar 

11. Pudlák, P.: The lengths of proofs. In: Handbook of Proof Theory, Ed. S. Buss, (to appear)

    Google Scholar 

12. Razborov, A. A.: Lower bounds for propositional proofs and independence results in bounded arithmetic. In: Proc. of the 23rd ICALP, F.Meyer auf der Heide and B. Monien eds., LN in Computer Science, 1099, Springer-Verlag, (1996) 48–62

    Google Scholar 

13. Razborov, A. A.: Lower bounds for the polynomial calculus. (submitted)

    Google Scholar 

Download references