It happens in real life too

Everyone’s heard one of these legendary horror stories, in which this weird-looking guy at the back of the room sleeps through your whole Ph.D. dissertation talk…but when question time comes, stands up, and asks whether you’ve heard of the work of X from 50 years ago…? No? Well, your “Main Theorem” on slide 1 was his “Corollary 7.14″…
Well, I just witnessed it 🙂 Luckily, it wasn’t someone’s dissertation talk, but a seminar on a new result. It went something like this:

– (Speaker) So we have this new algorithm with running time O(2^{L^2}N) for this problem here, assuming that the input satisfies this and that…

-(Audience) Oh, this looks really nice! And what happens in this and that case, and how does it compare with algorithm X (answer: favorably).

– (Speaker) Let me tell you about the proof overview now: it goes through reduction step 1, then reduction step 2, …

– (Weird guy at the back, suddenly interrupting) So, doesn’t the obvious dynamic programming algorithm give you running time O(2^L N)?

– (Speaker) Sorry, dynamic what? What is a dynamic algorithm?

– (Audience, to themselves) uh oh….

– (Weird guy) Here is how it works (gives clear details; takes him about 2 minutes).

– (Speaker) Well, we have 25 minutes left…

I have to say, the speaker did a very good job at staying on his feet, being interested in the solution proposed, and still trying to take us through the main ideas of his own proof idea…in the end, it looked like some of it could be salvaged, and Speaker and Weird guy agreed to set up a meeting (in case any of the two recognizes his or herself, no harm meant: I actually quite enjoyed both the talk and the simple solution!).

Punch line: next time you come up with a new algorithm for a previously unexplored problem, the fact that you can’t google any papers on the subject doesn’t mean your algorithm is the best known 🙂

About Thomas

I am a professor in the department of Computing and Mathematical Sciences (CMS) at the California Institute of Technology, where I am also a member of the Institute for Quantum Information and Matter (IQIM). My research is in quantum complexity theory and cryptography.
This entry was posted in Uncategorized. Bookmark the permalink.

3 Responses to It happens in real life too

  1. Sorry, but isn’t it somewhat shameful for a theorist not to know what dynamic programming is? I guess this stuff is taught during the 1st or 2nd year to CS undergrads…

    • Thomas says:

      I didn’t quite specify the context for the seminar…I realize I made it sound like an algorithms talk, but the person giving the talk might not have described her or himself as a “theorist”, so we’ll have to excuse her or him! Now they know 🙂

    • aram says:

      There are so many things that I don’t know that are “shameful” and that are taught in intro classes. At a certain point you just have to give the seminar and wait for people to tell you what you missed.

      The real thing to be ashamed of is not admitting and thoroughly investigating a mistake once you become aware of it.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s