CSAIL Event Calendar: Previous Series
Algorithms for Deciding Satisfiability of Random Formulas
Speaker: Uriel Feige , Microsoft Research
Relevant URL: http://theory.lcs.mit.edu/theory-seminars/calendar.html
Deciding satisfiability of 3CNF formulas is one of the central NP-complete problems. We consider the average case complexity of this problem, where the input distributions are those of random 3CNF formulas of various densities (where the density of a formula is the ratio between number of clauses to number of variables). The goal is to design efficient algorithms that on almost every input formula either find a satisfying assignment, or prove that no satisfying assignment exists. We survey some results in this area, and motivate some of the questions that remain open.