On math in job talks

It's job talk season around the country, and this note from +Lance Fortnow  popped up on my twitter feed.

If you give a job talk to a general CS audience, every formula will count against you.

— Lance Fortnow (@fortnow) January 18, 2016

I was a little puzzled by this claim, and soon the following response from +Ryan Williams appeared

@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

At which point +Lev Reyzin chimed in with

.@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

My response to all of this was:

@rrwilliams @fortnow avoiding formulas seems like abject surrender. Ryan’s suggestion seems reasonable

— Suresh Venkat (@geomblog) 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").

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.

Reading With Purpose: A grand experiment

This is the preface to a set of notes I'm writing for a seminar this semester. It will be a fun and bumpy ride !

Reading research papers in mathematical disciplines takes training. A student’s natural tendency is to read a paper from beginning to end in a depth-first manner. Every time they get stuck at a concept, they branch down another path, and then another, to the point where even getting through an abstract for a paper can take days and is exhausting.
Needless to say, this is not the best way to read technical material of any kind, mathematical or otherwise. 

I have spent many hours explaining to my students how they should be reading papers, and if you’re reading this and you have students of your own, you’ve probably done the same. While I don’t claim to have the perfect method for reading any given paper, I’ve learnt over the years how to quickly skim a paper, flying over it and scanning the terrain as it were. I’ve learnt when to make a deep dive all the way to ground level, and when to resurface. And above all, I’ve learnt to distinguish the different reasons for reading technical material in the first place, and that each mode requires a different treatment. 

I’ve looked all over the web for good material to give to students to learn how to read papers in (theoretical) computer science. I’ve found a few short articles here and there: S. Keshav’s note on reading systems papers, Michael Mitzenmacher’s helpful document, a page by Jason Eisner, and the many blog posts by Terry Tao, to name a few. There are also a number of good short articles on reading mathematics that I’ve drawn some inspiration from. 

But none of these capture the essence of what I try to achieve in my reading and what I want my students to be able to do. It’s a kind of Thurstonian ideal of understanding: where the proof falls away and what you’re left with is a deep conceptual appreciation of how the parts of a proof (or a theorem, or a set of definitions) fit together, and what they really mean. 

Moreover, if one is to teach the art of reading, it is important not just to describe the goal, but to find a way to get there: with exercises, little practices, and muscle-strengthening activities. This is after all the difference between teaching and showing.

That is my motivation for this collection of notes. It is my attempt to demystify and systematize a set of tools for reading papers. It will not be complete, and it will likely not resemble how you read papers. But hopefully it provides one way of getting to the promised land.

SoCG-STOC Joint Workshops Call

As you all might know, in an event sure to get someone a Nobel Peace Prize, the Symposium on Computational Geometry (SoCG) and the Symposium on the Theory of Computing (STOC) will "sympose" together in Boston this year.

As part of this peace offensive designed to unite points and graphs, the combinatorial and the geometric, the Laplacian and the Hilbertian, (someone please stop me now...), there will be a day of overlap between the two conferences. The intention is to have a day of workshops on topics of interest to both communities, as well as two invited talks (by Timothy Chan and Santosh Vempala).

I'm one of the co-organizers of this joint day of workshops (together with Yusu Wang, Chandra Chekuri and Alex Andoni). And I strongly encourage you to consider putting together a proposal for a workshop/tutorial/other event that brings together folks from these communities.

For more details, please visit the workshops page. The deadline for submitting proposals is Feb 22, 2016. Proposals do not need to be very long - they merely need to answer specific questions as detailed in the CFP.

This is a great opportunity to expose the communities to topics that they might not ordinarily bump into, but could enjoy and benefit from. I'm very excited to see what ideas get tossed around, and am looking forward to the event. Kudos to the STOC and SoCG steering committees for making this happen.