Scheder, Domink

Title:The PPSZ k-SAT Algorithm on Formulas with Many Solutions 

Abstract:PPSZ is the fastest known algorithm for k-SAT, a central NP-complete problem. The algorithm is famous for being very simple to state and quite difficult to analyze. I will present recent work on the behavior of PPSZ on input formulas with many solutions.