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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International