New Insights into Computational Intractability

Date: 30 September - 4 October 2013

Location: Mathematical Institute, University of Oxford

Computational complexity theory deals with the central mystery of computation: What is feasible to compute, and what computational tasks will forever remain out of reach?  Although the main open questions (such as the Millennium Problem of P versus NP) continue to elude us, exciting progress has been reported on a number of fronts recently.  This workshop will bring together many leading researchers in the field of computational complexity theory, and provide a forum where they can share their perspectives on the new insights that have been obtained.

Speakers:  Scott Aaronson (MIT), Manindra Agrawal (IIT Kanpur), Eric Allender (Rutgers), Harry Buhrman (CWI Amsterdam), Peter Bürgisser (Paderborn), Stephen Cook (Toronto), Irit Dinur (Weizmann), Martin Dyer (Leeds), Lance Fortnow (Georgia Tech), Leslie Ann Goldberg (Liverpool), Paul Goldberg (Liverpool), Georg Gottlob (Oxford), Russel Impagliazzo (UCSD), Peter Jeavons (Oxford), Mark Jerrum (QMUL), Elias Koutsoupias (Oxford), Peter Bro Milterssen (Aarhus), Ketan Mulmuley (Chicago), Toniann Pitassi (Toronto), Rahul Santhanan (Edinburgh), Salil Vadhan (Harvard), Ryan Williams (Stanford)

This is one of four concurrent workshops held in association with the 2013 Clay  Research Conference.