Deciding satisfiability of 3CNF formulas is one of the centralNP-complete problems. We consider the average case complexity of this problem, where the input distributions are those of random3CNF formulas of various densities (where the density of a formulais the ratio between number of clauses to number of variables).The goal is to design efficient algorithms that on almost everyinput formula either find a satisfying assignment, or prove thatno satisfying assignment exists. We survey some results in this area, and motivate some of the questions that remain open.

Bio Sketch:

Uriel Feige is a Principal Researcher in Microsoft Research, and a Professor at the Weizmann Institute (currently on leave). His

main research interest is that of coping with NP-hard problems, including design of approximation algorithms, proving hardness

of approximation results, and rigorous analysis of heuristics. For work in these areas he received (jointly with others) the Godel

Prize in 2001 and the SIAM Outstanding Paper Prize in 2005.

Thursday, November 16, 2006

3:00 pm - 4:15 pm

Wu & Chen Auditorium

101 Levine Hall