Short Propositional Refutations for Dense Random 3CNF Formulas

Sebastian Müller, Iddo Tzameret

Random 3CNF formulas constitute an important distribution for measuring the average-case behavior of propositional proof systems. Lower bounds for random 3CNF refutations in many p…