Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with propositional proofs:
TR00-087 | 14th November 2000
Albert Atserias, Nicola Galesi, Pavel Pudlak

Monotone simulations of nonmonotone propositional proofs

We show that an LK proof of size $m$ of a monotone sequent (a sequent

that contains only formulas in the basis $\wedge,\vee$) can be turned

into a proof containing only monotone formulas of size $m^{O(\log m)}$

and with the number of proof lines polynomial in $m$. Also we show

... more >>>

TR03-004 | 24th December 2002
Eli Ben-Sasson, Prahladh Harsha

Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games

We present a simple proof of the bounded-depth Frege lower bounds of
Pitassi et. al. and Krajicek et. al. for the pigeonhole
principle. Our method uses the interpretation of proofs as two player
games given by Pudlak and Buss. Our lower bound is conceptually
simpler than previous ones, and relies ... more >>>

ISSN 1433-8092 | Imprint