In this talk, we will try to present a self-contained simplified proof of hardness of random log(n)-CNF formulas in Cutting Planes. This result was proven by Hrubes, Pudlak, and independently by Fleming, Pankratov, Pitassi and Robere. In both papers, the authors reduce the considered question to the lower bound on monotone circuits and use Jukna's criteria to show the desired result. Instead of it, we do some direct bottleneck counting and discuss related open problems.


Video Recording