SAT Solving and Complexity Theory 

My goals for this talk are:

• To reacquaint you with complexity theory, and explain the "relativization barrier" to lower bounds
• Tell you about the state of the art regarding P versus NP 
• Tell you how SAT solving could help prove new theorems in complexity theory!

Ryan Williams, IBM Almaden Research Center, San Jose, USA

Josef Raviv Fellow at IBM since September 2009