We introduce the notion of {\em natural} proof. We argue that the known proofs of lower bounds on the complexity of explicit Boolean functions in non-monotone models fall within our definition of natural. We show based on a hardness assumption that natural proofs can't prove superpolynomial lower bounds for general ... more >>>

We introduce a new approach to construct extractors -- combinatorial objects akin to expander graphs that have several applications. Our approach is based on error correcting codes and on the Nisan-Wigderson pseudorandom generator. An application of our approach yields a construction that is simple to describe and analyze, does not ... more >>>

We give the first construction of a pseudo-random generator with optimal seed length that uses (essentially) arbitrary hardness. It builds on the novel recursive use of the NW-generator in a previous paper by the same authors, which produced many optimal generators one of which was pseudo-random. This is achieved in ... more >>>

We present a weaker variant of the PCP Theorem that admits a significantly easier proof. In this variant the prover only has $n^t$ time to compute each bit of his answer, for an arbitray but fixed constant $t$, in contrast to being all powerful. We show that 3SAT is accepted ... more >>>