BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Hardness Condensation Razborov, Alexander


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International