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. See other events that are part of Theory Colloquium Fall 2006 |
