Abstract
Random CNF formulas are one of the few candidates that are expected to be hard to refute in any proof system. One of the frontiers in the direction of proving lower bounds on these formulas is the k-DNF Resolution proof system (aka Res(k)). In this talk we present a new lower bound that based only on the expansion property of the underlying dependency graph of random formula. Joint work with Anastasia Sofronova.