Exponential time complexity

At the next three group meetings or so, I’ll try to give a very concrete introduction to exponential time complexity, including some very recent and exciting results (none of them mine). Here’s the plan, expressed in terms of papers I want to mention:

21 Sep: On Problems without Polynomial Kernel, Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin (ICALP 2008). Infeasibility of instance compression and succinct PCPs for NP, Lance Fortnow, Rahul Santhanam (STOC 2008)

28 Sep: On the Possibility of Faster SAT Algorithms, Mihai Pătraşcu and Ryan Williams (SODA 2010).

5 Oct: (cancelled).

A lot of exciting stuff is happening in this area right now, in fact, we just had a proposal for a 2010 Dagstuhl seminar accepted: Exact Complexity of NP-hard Problems.

0 Responses to “Exponential time complexity”


  1. No Comments

Leave a Reply

You must login to post a comment.