Russell Impagliazzo, Pavel Pudlak, Jiri Sgall

Razborov~\cite{Razborov96} recently proved that polynomial

calculus proofs of the pigeonhole principle $PHP_n^m$ must have

degree at least $\ceiling{n/2}+1$ over any field. We present a

simplified proof of the same result. The main

idea of our proof is the same as in the original proof

of Razborov: we want to describe ...
more >>>

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

We present the best known separation

between tree-like and general resolution, improving

on the recent $\exp(n^\epsilon)$ separation of \cite{BEGJ98}.

This is done by constructing a natural family of contradictions, of

size $n$, that have $O(n)$-size resolution

refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations.

This result ...
more >>>

Pavel Pudlak

We consider some problems about pairs of disjoint $NP$ sets.

The theory of these sets with a natural concept of reducibility

is, on the one hand, closely related to the theory of proof

systems for propositional calculus, and, on the other, it

resembles the theory of NP completeness. Furthermore, such

more >>>