Easy memory aides

Certain memory aides are so ... well.. memorable that they stick in your mind exactly the way they should. Here are three that I've heard of:

• Keeping track of the Baltic states: I think I heard this from +Fernando Pereira - They are alphabetical in order from north to south. So it's Estonia, Latvia and then Lithuania. 
• Converting between miles and kilometers: This is a particularly geek-friendly mnemonic - If the value in miles is (close to) a Fibonacci number, the value in kilometers is (close to) the next Fibonacci number. This works because the golden ratio is very close to the miles-to-km conversion factor.
• Keeping track of type-I/type-II errors: I heard this one on twitter the other day, and it goes like this. In the story of the boy who cried wolf, the errors appear in order. 

Things I need memory aides for:

• Bernstein vs McDiarmid vs Azuma, or different Chernoff bounds in general. 
• Jensen's inequality, so I don't have to constantly draw the picture of the convex function to derive it.
• Submodularity vs supermodularity: I know you add the diagonals and compare them, but which way is which???

Others? 

TheoryFest at STOC 2017.

(ed: I can't believe it's been four months since my last post. Granted, I've been posting over at algorithmicfairness.wordpress.com, but still. Time to turn in my theory card...)

One of the things I've been doing is helping out with the STOC TheoryFest this summer. Specifically, I've been on the plenary talks committee that was tasked with identifying interesting papers from other parts of CS and beyond that might be interesting for a STOC audience to hear about. After many months of deliberations, we're finally done! Boaz has more details over at his blog.

Do take a look at the papers. Boaz has a great summary for each paper, as well as links to the sources. You'll see a pretty decent coverage of different topics in CS, including even some theory B !!

But more importantly, please do register for STOC! This year, the organizers are making a real effort to restructure the conference to make it more accessible with a diversity of events like the plenary talks, tutorials, and workshops, and there should be something for everyone. Early registration ends on May 21, so click that link now.

In this day and age, I don't need to emphasize the importance of standing up and being counted. If you've ever grumbled about the old and stultifying format of STOC, this is your chance to vote with your feet. A big success for TheoryFest 2017 will surely encourage more along these lines in future years.

A short course on FATML -- and a longer course on ethics in data science.

I'm at IIIT Allahabad teaching a short course on fairness, accountability and transparency in machine learning. This is part of the GIAN program sponsored by the Government of India to enable Indian researchers from outside the country to come back and share their knowledge. The clever pun here is that GIAN -- which stands for Global Initiative of Academic Networks -- also means 'knowledge' in Hindi (ज्ञान).
Anyway, I'm excited to be teaching a course on this topic, and that has forced me to organize my thoughts on the material as well (which has already led to some interesting insights about how the literature fits together). I'm writing out my lecture notes, and one of the energetic students at the course has kindly offered to help me clean them out, so I hope to have a set of notes in less than a year or so. 

Note that the syllabus on the linked page is evolving: it will change over the course of the next few days as I add more things in. 

I'm also excited to to be teaching a (brand-new) undergraduate course on ethics and data science next fall. I'll have more to say about this as I prepare material, but any suggestions/materials are welcome. 

Modeling thorny problems.

Today, I got into a nice twitter discussion with former colleague and NLPer extraordinaire (even when he hates on algorithms) Hal Daumé. Here's what he said:

one consistent msg I heard re ethics/policy today is that even though no one really knows the right answer, the question is how to move fwd

— Hal Daumé III (@haldaume3) October 19, 2016

akin to "perfect is the enemy of the good", but I think different because we don't even know how to measure "perfect" :)

— Hal Daumé III (@haldaume3) October 19, 2016

To which I replied:

@haldaume3 right. I think of this as a partial order rather than total. Measure better along chains and argue between maximal elements

— Suresh Venkat (@geomblog) October 19, 2016

It seemed to be worth fleshing this out a little.

In the work we've been doing in algorithmic fairness, one of the trickiest issues has been attempting to mathematically capture the different (and very slippery) notions of fairness, bias, and nondiscrimination that are used in common parlance and in the more technical literature on the subject. As Hal noted in his tweet above, these are very difficult problems for which no one really has the right answer.

How then does one make forward progress? In my view, framing is an essential part of the discussion, and one that we tend not to consider very explicitly in computer science. That is to say, deciding how to ask the question has much more impact on forward progress than the specific nature of the solutions.

This is not news if you look at politics, the law, policy discussions or the social sciences in general. But it matters a great deal as CS starts dealing with these issues because the choices we make in how to pose questions change the kinds of progress we hope to make. (while I realize that "questions matter, not solutions" is one of the oldest tropes in all of research, modeling issues like ethics and fairness requires a whole other dimension of framing -- see this nifty reframing of the editorial role of Facebook for example)

Specifically, I think of these problems as points in a partial order. It's relatively easy to talk about progress along a chain: that's what CS is really good at. But it's important to realize that we're living in a partial order, and that when we argue about different approaches, we might actually be arguing about fundamentally different and incomparable issues.

So then what happen when we reach different maximal elements (or imagine ideal maximal elements)? That's where the arguments center around beliefs, axioms and worldviews (not surprisingly, that's how we're thinking about fairness). But then the arguments are of a different nature altogether, and realizing that is very important. It's no longer an issue of what running time, what approximation ratio, what generalization bound you can get, but rather what aspects you're trying to capture and what you're leaving out.

So while it might seem that the problems we face in the larger realm of algorithms and ethics are irreducibly complex (they are) there's value in understanding and creating a partial order of formulations and making progress along different chains, while also arguing about the maximal elements.

Coda: 

One day, when I have nothing to do (ha!) I might attempt to write down some thoughts on how to model ill-structured problems mathematically. And it's not just about algorithmic fairness -- although that tests my skills royally. Any kind of mathematical modeling requires certain skills that we don't learn when we learn to solve crisply defined problems.

For example, one aphorism I found myself spouting some weeks ago was

Model narrowly; solve broadly. 

This was in the context of a discussion I was having with my undergraduate student about a problem we're trying to formalize. She had a nice model for it, but it was very general, and I worried that it was capturing too much and the essential nature of the problem wasn't coming through. Of course when it comes time to solve a problem though, using general hammers is a good place to start (and sometimes finish!).

Axiomatic perspective on fairness, and the power of discussion

Sorelle Friedler, Carlos Scheidegger and I just posted a new paper on the arxiv where we try to lay out a framework for talking about fairness in a more precise way. 

The blog post I link to says more about the paper itself. But I wanted to comment here on the tortuous process that led to this paper. In some form or another, we've been thinking about this problem for two years: how do we "mathematize" discussions of fairness and bias? 

It's been a long and difficult slog, more than any other topic in "CS meets X" that I've ever bumped into. The problem here is that the words are extremely slippery, and refract completely different meanings in different contexts. So coming up with notions that aren't overly complicated, and yet appear to capture the different ways in which people think about fairness was excruciatingly difficult. 

We had a basic framework in mind a while ago, but then we started "testing" it in the wild, on papers, and on people. The more conversations we had, the more we refined and adapted our ideas, to the point where the paper we have today owes deep debts to many people that we spoke with and who provided nontrivial conceptual challenges that we had to address. 

I still have no idea whether what we've written is any good. Time will tell. But it feels good to finally put out something, however half-baked. Because now hopefully the community can engage with it. 

Congrats to John Moeller, Ph.D

My student +John Moeller (moeller.fyi) just defended his Ph.D thesis today! and yes, there was a (rubber) snake-fighting element to the defense.

John's dissertation work is in machine learning, but his publications span a wider range. He started off with a rather hard problem: attempting to formulate a natural notion of range spaces in a negatively-curved space. And as if dealing with Riemannian geometry wasn't bad enough, he was also involved in finding approximate near neighbors in Bregman spaces. He's also been instrumental in my more recent work in algorithmic fairness.

But John's true interests lie in machine learning, specifically kernels. He came up with a nice geometric formulation of kernel learning by way of the multiplicative weight update method. He then took this formulation and extended it to localized kernel learning (where you don't need each kernel to work with all points - think of it like a soft clustering of kernels).

Most recently, he's also explored the interface between kernels and neural nets, as part of a larger effort to understand neural nets. This is also a way of doing kernel learning, in a "smoother" way via Bochner's theorem.

It's a great body of work that required mastery of a range of different mathematical constructs and algorithmic techniques.  Congratulations, John!

FOCS workshops and travel grants.

Some opportunities relating to the upcoming FOCS.

• Alex Andoni and Alex Madry are organizing the workshops/tutorials day at FOCS, and are looking for submissions. The deadline is August 31, so get those submissions ready!
• Aravind Srinivasan and Rafi Ostrovsky are managing travel and registration grants for students to go to FOCS. The deadline for applications is September 12. 

Of course FOCS itself has an early registration deadline of September 17, which is also the cutoff for hotel registrations. 

Pokégyms at Dagstuhl

Yes, you read that correctly. The whole of Dagstuhl is now a Pokégym and there are Pokémon wandering the streets of Wadern (conveniently close to the ice cream shop that has excellent ice cream!)

Given this latest advancement, I was reminded of Lance Fortnow's post about Dagstuhl from back in 2008 where he wistfully mourned the fact that Wifi now meant that people don't hang out together.

Times change. I am happy to note that everything else about Dagstuhl hasn't changed that much: we still have the book of handwritten abstracts for one thing.

Carl Zimmer's series on exploring his genome

If you haven't yet read Carl Zimmer's series of articles (one, two, three), you should go out and read it now!

Because after all, it's Carl Zimmer, one of the best science writers around, especially when it comes to biology.

But even more so because when you read the story of his personal quest to understand his genetic story in all its multifaceted glory, you understand the terrifying opportunities and dangers in the use of genetic information for predictive and diagnostic medicine. You also realize the intricate way that computation is woven into this discovery, and how sequences of seemingly arbitrary choices lead to actual conclusions about your genome that you now have to evaluate for risk and likelihood.

In a sense, this is the tale of the use of all computational approaches right now, whether it be in science, engineering, the social sciences, or yes, even algorithmic fairness. Zimmer uses the analogy with telescopes to describe his attempts to look at his genome, and this explanation is right on the money:

Early telescopes weren’t terribly accurate, either, and yet they still allowed astronomers to discover new planets, galaxies, and even the expansion of the universe. But if your life depended on your telescope — if, for example, you wanted to spot every asteroid heading straight for Earth — that kind of fuzziness wouldn’t be acceptable.

And this quote from Robert Green, one of the geneticists who was helping Zimmer map out his genome:

Ultimately, the more you know, the more frustrating an exercise it is. What seemed to be so technologically clear and deterministic, you realize is going through a variety of filters — some of which are judgments, some of which are flawed databases, some of which are assumptions about frequencies, to get to a best guess.

 In this is a message for all of us doing any kind of data mining.

NIPS Reviewing

This year, NIPS received over 2400 submissions. That's -- well --- a lot!

As a reviewer, I have been assigned 7 papers (note that this number will be utterly incomprehensible to theoryCS PC members who think that 30 papers is a refreshingly low load).

But none of that is as interesting as what NIPS is trying this year. From the PC Chairs:

New this year, we ask you to give multiple scores for technical quality, novelty, impact, clarity, etc. instead of a single global score. In the text boxes, please justify clearly all these scores: your explanations are essential to the ACs to render and substantiate their decision and to the authors to improve their papers.

Specifically, the categories are:

• Technical quality
• Novelty/originality
• Impact/usefulness
• Clarity and presentation

and there are also a few qualitative categories (including the actual report). Each of the numerical categories are on a 1-5 scale, with 3 being "good enough".

I've long felt that asking individual reviewers to make an accept/reject judgement is a little pointless because we lack the perspective to make what is really a zero-sum holistic judgement (at least outside the top few and the long tail). Introducing this multidimensional score might make things a little more interesting.

But I pity the fate of the poor area chairs :).

The Man Who Knew Infinity

I generally avoid movies about mathematicians, or mathematics.

I didn't watch Beautiful Mind, or even the Imitation game. Often, popular depiction of mathematics and mathematicians runs as far away from the actual mathematics as possible, and concocts all kinds of strange stories to make a human-relatable tale.

Not that there's anything wrong with that, but it defeats the point of talking about mathematics in the first place, by signalling it as something less interesting.

So I was very worried about going to see The Man Who Knew Infinity, about Srinivas Ramanujan and his collaboration with G. H. Hardy. In addition to all of the above, watching movies about India in the time of the British Raj still sets my teeth on edge.

To cut a long story short, I was happy to be proven completely wrong. TMWKI is a powerful and moving depiction of someone who actually deserves the title of genius. The movie focuses mostly on the time that Ramanujan spent at Cambridge during World War I working with Hardy. There are long conversations about the nature of intuition and proof that any mathematician will find exquisitely familar, and even an attempt to explain the partition function. The math on the boards is not hokey at all (I noticed that Manjul Bhargava was an advisor on the show).

You get a sense of a real tussle between minds: even though the actual discussions of math were only hinted at, the way Hardy and Ramaujan (and Littlewood) interact is very realistic. The larger context of the war, the insular environment of Cambridge, and the overt racism of the British during that period are all signalled without being overbearing, and the focus remains on the almost mystical nature of Ramanujan's insights and the struggle of a lifelong atheist who finally discovers something to believe in.

It took my breath away. Literally. Well done.

Google Recruiter Survey: Tell us what you think!

(ed: I can't believe it's been almost three months since I posted. Maintaining two blogs and twitter is more work than one might think)

Hello,
  Thank you for applying to recruit me to Google. I'm continuously working to provide a great experience to my recruiters throughout the hiring process, so I greatly value any feedback you’re willing to share about your experience—both what’s going well and what needs work.

Please share your feedback through my recruiter experience survey, which will be open from now through Monday, May 44. The survey should take less than 15 seconds to complete, and you can skip over any questions you prefer not to answer. Please keep in mind that your responses are not confidential, and will be used for humor improvements—not in decisions as to who I choose to allow to recruit me.

I absolutely do not love chatting with recruiters, though I sometimes receive more emails than I can respond to and have to prioritize questions regarding technical difficulties. Below are a few of my most frequently asked questions (FAQs) that may provide the answer you need.

Thank you for your time and have a great day,

Suresh, Suresh Venkatasubramanian Recruitment Experience Team.

FAQs
I never received feedback on my recruitment email - can you give me feedback?

I'm pretty limited on what I have access to within your recruiter profile (to ensure that my brain doesn't melt). I don't particularly mind you feeling confused about the outcome. Therefore, I suggest reaching out to your friends and family  if you have specific questions regarding your attempt to  recruit me at Google.


I’d like to provide more input on your process - should I email that over?
Please use the open ended comments at the end of the survey to leave any anecdotal feedback or additional thoughts. It's in the handy box titled /dev/null. This ensures your thoughts are not saved as I ignore aggregate feedback to share with my internet following.

 

Time to cluster !

After many blog posts, much discussion, and some contract back and forth, I'm happy to announce that +Sergei Vassilvitskii and I have signed a contract with Cambridge University Press to write a book on clustering.

"What's that?", you say. "You mean there's more than one lecture's worth of material on clustering?". 

In fact there is, and we hope to produce a good many lectures' worth of it.

Information on the book will be available at http://clustering.cc. It currently forwards to my blog page collecting some of the posts we wrote, but it will eventually have its own content.

Now the painful part starts.

Cartograms only exist in years divisible by 4...

Every four years, America suddenly discovers that it likes football soccer. Every four years also, America discovers the existence of the cartogram. The last time I ventured into this territory (here's the link, but link rot has claimed the images), I was accused of being a liberal shill. And here's more on cartograms and the 2004 election.

Teaching a process versus transmitting knowledge

Ta-Nehisi Coates is forced to state who he's voting for in the next election. He struggles with the act of providing an answer, because

Despite my very obvious political biases, I’ve never felt it was really my job to get people to agree with me. My first duty, as a writer, is to myself. In that sense I simply hope to ask all the questions that keep me up at night. My second duty is to my readers. In that sense, I hope to make readers understand why those questions are critical. I don’t so much hope that any reader “agrees” with me, as I hope to haunt them, to trouble their sense of how things actually are.

In the last few years, I've had to think a lot about what it means to teach a core class (algorithms, computational geometry) for which most material is already out there on the Web. I think of my role more as an explorer's guide through the material. You can always visit the material by yourself, but a good tour guide can tell you what's significant, what's not, how to understand the context, and what is the most suitable path (not too steep, not too shallow) through the topic.

That's all well and good for teaching content. But when it comes to teaching process, for example with my Reading With Purpose seminar, I have to walk a finer line. I've spent a lot of time with my own thoughts trying to deconstruct how I read papers, and what parts of that process are good and useful to convey, and what parts are just random choices.

I want to make sure my students are "haunted and troubled" by the material they read. I want them to learn how to question, be critical, and find their own way to interrogate the papers. I want them to do the same critical deconstruction of their own process as well.

On the other hand, the "stand-back-and-be-socratic" mode is very hard to execute without it seeming like I'm playing an empty game that I have no stakes in, and so I occasionally have to share my "answers". I fear that my answers, coming from a place of authority, will push out their less well-formed but equally valid ways of approaching the material.

I deal with this right now by constantly trying to emphasize why different approaches are ok, and try to foster lots of class discussion, but it's a struggle.

Note: I'm certain that this is a solved problem in the world of education, so if anyone has useful tips I'm eager to get pointers, suggestions, etc. 

Who owns a review, and who's having the conversation ?

I had floated a trial balloon (this is election season after all!) about making reviews of my papers public. I had originally thought that my coauthors would object to this plan, for fear of retribution from reviewers, or feelings of shame about the reviews (things that I was concerned with).

What I didn't expect was strong resistance from potential reviewers, with people going as far as to say that a) they might refuse to review my papers in the future or b) I'd be deterring reviewers from doing any kind of reviewing if my idea caught on.

I was surprised by this response. And then I was surprised by my surprise. And I realized that the two perspectives above (mine, and the commenters) come from fundamentally different views on the relation between reviewer, author and arbiter (aka the PC/journal).

This post is an attempt to flesh that out.

Dramatis Personae:

There are three players in this drama: the (A)uthor, (R)eviewer, and the PC chair/editor whom we'll call the (J)udge. A submits a paper, R reviews it, and J (informed by R) makes a final decision.

So how do they interact ?

View 1: A and R have a conversation.

My idea of publishing reviews comes from this perspective. R looks over the paper and discusses it (anonymously) with A, facilitated by J. The discussion could be one-shot, two-shot, or a longer process. The discussion is hopefully informative and clarifying. Ideally it improves the paper. This is an approximation of what happens in a journal review, and I think is how many authors imagine the process as working.

Posting the discussion is then helpful because it provides some context for the work (think of it like the comments section of a page, but chaperoned, or an overheard research discussion at a cafe).

It's also helpful to keep all parties honest. Reviewers aren't likely to write bad reviews if they know it might become public. In fact, a number of conferences that I'm involved with are experimenting with making reviews public (although this is at the behest of J, not A).

View 2: J and R have a conversation

J requests that R make an assessment of the paper. R reads it over, forms an opinion, and then has a short conversation with J. In a conference setting, J has other constraints like space and balance, but R can at least provide a sense of whether the paper is above the bar for publication or not. This is how most reviewers imagine the process working.

At the end of the process, J decides (in concert with R) how much of the review to share with A, ranging from just the decision bit to the entire review (I don't know of any conference that shares the conversation as well).

Who owns the review, and who's having the conversation? 

The difference between these two perspectives seems to be at the root of all the complaining and moaning about peer review in our community (I'm not talking about the larger issues with peer review in say the medical community). Authors think that they're operating in View 1, and are surprised at the often perfunctory nature of the review, and the seeming unwillingness of reviewers to engage in a discussion (when for example there's a rebuttal process).

Reviewers on the other hand live in View 2, and are begrudging at best with comments that are directed at the author. In fact, the harshness and seeming arbitrariness of the review (as perceived by the author) can be explained simply as: they weren't really written for you to read !

The view also changes one's perspective on ownership. If a review is a conversation between J and R, then it's an outrageous idea to let A (who's only getting the review out of kindness) publish it for all to see. But if the review is meant to help A write a better paper, then why can't A publish the discussion ?

So what's the upshot of all of this ? 

There are many good reasons not to publish my reviews. Probably the most important reason (as was pointed out to me) is that the very fact that I can speculate out loud about doing this demonstrates a kind of privilege. That is to say, if I do publish critical reviews of my work, I'm likely to take less of the blame and more of the credit than coauthors who are more disadvantaged (students, minorities, women). If you don't believe me, I encourage you to read Tamara Munzner's series on a major brouhaha in the Vis community triggered by a public review (posted by a reviewer).

Another good reason is that if some of my coauthors object (and so I don't post reviews for papers with them) and others don't (and so I do), that in itself sends signals of the "what are you afraid of" form that can again fall disproportionately on my coauthors.

A third reason is that anonymous never stays that way. Eventually, if enough reviews get posted, some enterprising NLPer will write a simple predictor to identify styles in reviews, cluster reviews likely written by the same individual, and then cross-reference with any leaked information (for example if they're on a PC) to leak some information.

But here are some bad reasons (that were posted in response to my post):

• Reviewers will be scared away and it's hard enough to get them to review in the first place ? Really? Reviewers have such fragile egos ? This is a classic slippery slope argument with no real basis in truth. And given how many younger researchers are desperate to get a chance to review papers, I suspect that as soon as someone stops, someone else will pick up the slack.
• Reviewers own the copyright of their writing, and it would be a copyright violation. IANAL, but I don't think the people raising this point are either. And this is very backwards reasoning. We can decide in good faith whether we think posting reviews is a good idea or not, but using legal arguments seems like a cop-out. There are always ways to fix that at PC formation time. 
• It's ethically wrong to post reviews. I don't understand how it's an ethical issue. The only way there could be an ethical issue is if reviewers were promised that the reviews would stay confidential. But that's never the case: reviewers are exhorted to share the reviews with the authors. And again, this has the causality backward. Whether we should publish reviews or not should not depend on what we currently might have in the way of expectations. 

I should note that NSF proposal reviews (that are much more secret) are shared with the author without conditions, and there's no prohibition against posting them. In fact seeing proposal reviews can be a great way to understand how reviewers think. 

Bottom line: I won't be posting my reviews any time soon, which is a pity because I genuinely think that this provides a degree of accountability for reviewers that they currently don't have. But it was very interesting to think through this out loud and understand the perspective others brought to the discussion. 

ITA FTW: Bayesian surprise and eigenvectors in your meal.

I've been lounging in San Diego at my favorite conference, the Information Theory and Applications workshop. It's so friendly that even the sea lions are invited (the Marine Room is where we had the conference banquet).

Sadly this year I was mired in deadlines and couldn't take advantage of the wonderful talks on tap and the over 720 people who attended. Pro tip, ITA: Could you try to avoid the ICML/KDD/COLT deadlines next time :) ?

ITA always has fun events that our more "serious" conferences should learn time. This time, the one event I attended was a Man vs Machine cookoff. Which I thought was particularly apropos since I had just written a well-received article with a cooking metaphor for thinking about algorithms and machine learning.

The premise: Chef Watson (IBM's Watson, acting as a chef) designs recipes for dinner (appetizer/entree/dessert) with an assist from a human chef. Basically the chef puts in some ingredients and Watson suggests a recipe (not from a list of recipes, but from its database of knowledge of chemicals, what tastes 'go well together' and so on. This was facilitated by Kush Varshney from IBM, who works on this project.

Each course is presented as a blind pairing of Watson and Human recipes, and its our job to vote for which one we think is which.

It was great fun. We had four special judges, and each of us had a placard with red and blue sides to make our votes. After each course, Kush gave us the answer.

The final score: 3-0. The humans guessed correctly for each course. The theme was "unusualness": the machine-generated recipes had somewhat stranger combinations, and because Watson doesn't (yet) know about texture, the machine-recipes had a different mouthfeel to them.

This was probably the only time I've heard the words 'Bayesian surprise' and 'eigenvector' used in the context of food reviews.

Making all my reviews public (and annotated): A question.

I was reading a post on G+ about a musician who keeps all her performance reviews on her website and annotates them with a response. Not to "fight back", but to add to the reviews (that are occasionally negative).

I'm very tempted to do the same thing myself with my submissions. I think this will provide more clarity about the nature of the review process, about the often honest and revealing discussions that take place behind the peer-review walls, and about how subtleties in the writing can change the perception of a work. I suspect that as a consequence I'll be more circumspect about submitting something half-baked (which might be a good thing). I'll have to be careful not to get defensive in my responses to the reviews (which is always hard). And I may not be able to get away as easily with "changing the introduction" to get a paper in (which happens shockingly often).

Of course the biggest problem will be getting my co-authors (who are often my students) to agree beforehand. So here's my question:

Would you work with me if you knew I was planning to make all my reviews public? 

On "the moral hazard of complexity-theoretic assumptions"

(ed: In a recent CACM editorial,  CACM editor-in-chief +Moshe Vardi  discussed Babai's result on graph isomorphism and the recent hardness result for edit distance in the context of a larger discussion on the significance of complexity-theoretic assumptions. +Piotr Indyk  (one of the authors of the edit distance result and an occasional guest blogger) posted the following as a response. This response has also been posted as a comment on Moshe's post.)

(ed: Update: After Piotr posted the comment, Moshe responded, and then Piotr responded again. Please visit the article page to read the exchange between the two). 

In a recent CACM editorial, Dr. Vardi addresses what he calls a "a moral hazard of complexity-theoretic assumptions" and "a growing gap between current theory and practice of complexity and algorithms". Given that the article mentions a paper that I am a co-author of [ "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)", STOC'15], I believe it is appropriate for me to respond. In short, I believe that much of the analysis in the article stems from a confusion between press coverage and the actual scientific inquiry. Indeed, it is unclear whether Dr. Vardi addresses what he believes to be a "media" phenomenon (how journalists describe scientific developments to a broad public) or a "scientific" phenomenon (how and why the scientists make and use assumptions in their research and describe them in their papers). In order to avoid conflating these two issues, I will address them one by one, focusing on our paper as an example.

1. Media aspects: The bulk of the editorial is focused on some of the press coverage describing recent scientific developments in algorithms and complexity. In particular, Dr. Vardi mentions the title of a Boston Globe article covering our work ("For 40 Years, Computer Scientists Looked for a Solution that Doesn't Exist.") . As I already discussed this elsewhere (https://liorpachter.wordpress.com/2015/08/14/in-biology-n-does-not-go-to-infinity/#comment-4792 ), I completely agree that the title and some other parts of the article leave a lot to be desired. Among many things, the conditional aspects of the result are discussed only at the end of the article, and therefore are easy to miss. At the same time, I believe some perspective is needed. The inaccuracy or confusion in popular reporting of scientific results is an unfortunate but common and longstanding phenomenon (see e.g., this account https://lpsdp.files.wordpress.com/2011/10/ellipsoid-stories.pdf of press coverage of the famous Khachiyan's linear programming algorithm in the 1970s). There are many reasons for this. Perhaps the chief one is the cultural gap between the press and the scientists, where journalists emphasize accessibility and newsworthiness while scientists emphasize precision. As a result, simplification in scientific reporting is a necessity, and the risk of oversimplification, inaccuracy or incorrectness is high. Fortunately, more time and effort spent on both sides can lead to more thorough and nuanced articles (e.g., see https://www.quantamagazine.org/20150929-edit-distance-computational-complexity/ ). Given that the coverage of algorithms and complexity results in popular press is growing, I believe that, in time, both scientists and journalists will gain valuable experience in this process.
2. Scientific aspects: Dr. Vardi also raises some scientific points. In particular:
   •  Dr. Vardi is critical of the title of our paper: "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false).". I can only say that, given that we are stating the assumption explicitly in the title, in the abstract, in the introduction, and in the main body of the paper, I believe the title and the paper accurately represents its contribution.
   • Dr. Vardi is critical of the validity of SETH as a hardness assumption: this question is indeed a subject of a robust discussion and investigation (see e.g., the aforementioned Quanta article). The best guess of mine and of most of the people I discussed this with is that the assumption is true. However, this is far from a universal opinion. Quantifying the level of support for this conjecture would be an interesting project, perhaps along the lines of similar efforts concerning the P vs. NP conjecture ( https://www.cs.umd.edu/~gasarch/papers/poll2012.pdf ). In any case, it is crucial to strengthen the framework by relying on weaker assumptions, or replacing one-way reductions with equivalences; both are subjects of ongoing research. However, even the existing developments have already led to concrete benefits. For example, failed attempts to prove conditional hardness of certain problems have led to better algorithms for those tasks.

Finally, let me point out that one of the key motivations for this line of research is precisely the strengthening of the relationship between theory and practice in complexity and algorithms, a goal that Dr. Vardi refers to as an important challenge. Specifically, this research provides a framework for establishing evidence that certain computational questions cannot be solved within concrete (e.g., sub-quadratic) polynomial time bounds. In general, I believe that a careful examination of the developments in algorithms and complexity over the last decade would show that the gap between theory and practice is shrinking, not growing. But that is a topic for another discussion.

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.