noc21-cs53-Lec08
Dec 9, 2023
Description: The lecture finishes the Razborov's proof on the hardness of Clique function computable by monotone circuits. In the process, we state, and later prove, the famous Sunflower Lemma of Erdős and Rado.
Description: The lecture finishes the Razborov's proof on the hardness of Clique function computable by monotone circuits. In the process, we state, and later prove, the famous Sunflower Lemma of Erdős and Rado.