Open Collections

Description

Hardness condensation (or compression) is a technique that allows to drastically reduce the number of variables in a contradictory formula while preserving its hardness for a proof system. It is based on substituting variables with more complicated formulas in such a way that the dependence relation between old and new variables makes a good expander. In this talk we will review several applications of this technique; a significant part of it will be devoted to actual proofs of one or, time permitting, even two results.