I was a little puzzled by this claim, and soon the following response from +Ryan Williams appearedIf you give a job talk to a general CS audience, every formula will count against you.— Lance Fortnow (@fortnow) January 18, 2016
At which point +Lev Reyzin chimed in with@fortnow Say a clear sentence in English with good slide pictures, and follow with "In complexity, this means <formula>" Never failed for me— R. Ryan Williams (@rrwilliams) January 18, 2016
My response to all of this was:.@geomblog @rrwilliams @fortnow In math, you're *supposed to* lose everyone by the end. On job market, I had separate talks for cs and math.— Lev Reyzin (@lreyzin) January 19, 2016
Above all, a job talk should be comprehensible to a general CS audience, for many of whom the last algorithms class they talk was 25 years ago, and for whom IP, PCPs or even approximation algorithms are strange unknown beasts. And so I understand the sentiment expressed in Lance's post ("don't get too technical").@rrwilliams @fortnow avoiding formulas seems like abject surrender. Ryan’s suggestion seems reasonable— Suresh Venkat (@geomblog) January 19, 2016
But avoiding formulas seems excessive. If you're expressing mathematical concepts, sometimes you need to be precise. Especially if your work hinges on being careful about these concepts. Thankfully, a good result has a nice intuitive explanation, and it's usually possible to do what Ryan suggested. For example, my favorite pitch for IP, PSPACE and the like is "A conversation is likely exponentially better than a monologue". (For why I'd be talking about IPs and PSPACE, you'll have to wait for my next post or two).
But couple that with the formal expression! Otherwise the more intuitive explanation seems like a giant hand wave that doesn't make any sense.
One of my standard rants when I'm explaining to students how to read theory papers is that they have to be able to go fluidly between notation and intuition, and that they have to mentally translate formalisms in a paper into intuition in order to really get what the paper is saying. But if we can't present both forms in a single setting, how is any non-expert to realize that the two are related ?
In short, if you're doing a job talk where I'm in attendance, don't be shy to put in formulas, but make sure to give some intuition for what the formalism is saying.