Beyond Worst Case Analysis -- Preparing a Talk

A few months ago, Tim Roughgarden mailed me to say was putting together a little workshop on the theme of Beyond Worst Case Analysis, and would I like to be one of the plenary speakers?  It sounded like an interesting topic, one I've certainly spoken off the cuff about on this blog from time to time.  And I enjoy any reasonably good excuse to get out to the Bay Area.  So I agreed.

The workshop announcement is here.  As you might imagine, what Tim DID NOT tell me at the time was that the other speakers were Avrim Blum, Bernard Chazelle, Uri Feige, Richard Karp, Dan Spielman, and Shang-Hua Teng.  That would have given me pause, to say the least.  Now I get to spend the summer thinking about how I'm going to give a talk that could still be deemed interesting in the company of this group of scholars.  No pressure, no pressure...

(Tim also failed to mention that he had actually taught a course on this whole subject.  Which, I should say, looks like a great course -- I'd love to swipe his notes and teach it myself some time.  Again, the bar here is higher than I had expected... let that be a lesson to everyone if Tim comes asking you for something...)

I will hopefully blog more on this topic as I prepare the talk, in order to get ideas and feedback from the community at large.  I figure that's one way to improve my talk.  Also, now that I've said I'm going to do that, hopefully it will get me working on the talk sooner rather than later.  (It's amazing how fast the summer goes by, and you fail to get done all the wonderful things you had planned to do over the summer...) 

But even now, you can help me out.  What directions or issues do you see in the theme of Beyond Worst Case Analysis, and what would you like to see in a talk on the subject?

(And if you get a chance, come to the workshop!)