As we begin January so begins the hiring season. In January CS
departments start sifting through candidates deciding whom to bring in
for interviews. Don't wait until you get your interview call, now is
the time to get your job talk ready.
A great job talk by itself won't guarantee you a job, but I've heard
of many an instance where a bad talk has ruined a candidate's chances
despite otherwise stellar credentials. A good job talk should achieve
three goals.
Explain your results.
Explain why your results are important.
Explain how you achieved your results.
Fail to do the first two and you will not get the job. We theorists
have a tendency to want to "wow" an audience with our clever
techniques but first you must spend several slides carefully giving an
intuitive description of your research and why those in the audience
should care about the results. Be sure and mention what your own
research is early in the talk and again at the end.
Know your audience, usually a broad spectrum of computer
scientists. You give a different talk to them than you would in a
regular theory seminar. Motivation and intuitive explanations of your
research are key.
Repeat the following mantra as you prepare your slides: Formulas
bad. Pictures good. Formulas bad. Pictures good.
Give a practice talk in your own department. Invite some people from
outside theory. Listen to the comments. Revise your talk. Repeat.
I would amplify one of Lance's comments: most departments consist primality of non-theorists, and largely of people who are not convinced they should hire a theorist. To counter this, I recommend making the entire first half of the talk something that _everyone_ in the department can understand and appreciate (in the second half you can sketch your techniques to illustrate your technical brilliance).
Keep in mind, also, that spending a lot of time on pedagogy will earn you points as someone who will likely be a good instructor. So don't be afraid to explain things, even if you think everyone ought to know them. Reminding an audience member of something they already know isn't insulting to them; assuming that they know something they don't _is_ insulting, especially if you imply that it's obvious.
Talk about future directions, but I suggest you do so broadly. Once saw a candidate who had great results, but his future work statement was based on mining the same very narrow (and very hard) problem, which was perceived as a negative.
Also, though it sounds silly, your behavior at meals during interviews is important. I can remember candidates who (a) drank too much (b) revealed their sexism by never addressing or even looking at the female at the table and (c) had awful, awful table manners. Needless to say, none of them got offers.
1. Should one talk his best work or thread his several main achievements together as a story (if that's possible)?
Showing a variety of interests is good, but you should be careful about putting a confusing mass of things in the talk. The talk should have a clear "take-home message" that everyone can understand; think carefully about what this message should be, and make sure it doesn't get lost. If your goal is to let people know that you have broad interests, you can also do that in your one-on-one meetings with the faculty.
2. Should one also talk about future directions?
Yes, with the caveat that the conclusion of the talk is a nice place to return to accessibility for everyone as opposed to diving deeper into the technical details. So future directions that a broad range of CS people can get excited about are good; but saying things like "in future work, we hope to use the fact that supersolvable groups have irreducible representations which are permutation matrices up to a phase in each row" is not.
Cris was a bit equivocal in his answer to the first question, so let me be a bit more definite: pick one topic. If you have a couple of papers which naturally bear on that topic, great, but don't force it. Sometimes you can make a good talk out of a single idea applied to multiple different topics, but that possibility isn't available to everyone.
In my experience, it almost never works when someone, even an otherwise good speaker, tries to squeeze two or three separate topics into a single talk (job talk or not), even when they are slightly related. Usually the first topic runs over and the others are shorted, and even when this doesn't happen, the question time is a mess.
Many places ask for a research statement. That is the place to tell the story connecting all your papers. You might refer to the overarching idea in your talk, but pick one result to focus on.
Excellent suggestions. One choice that I have seen work well is for a candidate to focus on one topic for about 40 minutes and then switch modes to paint the broader picture of themselves as a researcher for the last 5-10 minutes. This included an overview of other work they have done as well as the big picture for future directions. (Note that this only works if the other work being discussed is essentially as strong as the work being presented.)
"Also, though it sounds silly, your behavior at meals during interviews is important. I can remember candidates who (a) drank too much (b) revealed their sexism by never addressing or even looking at the female at the table and (c) had awful, awful table manners. Needless to say, none of them got offers."
Of course, as a candidate, you are likely to meet interviewers who have bad manners, are obnoxious, sexist, etc., but I guess as a candidate there is nothing you can do. Unless you know you don't want that job and then you can say something.