I recently reviewed a paper for AAAI that, briefly, described a novel polynomial-time algorithm for a hypothetical problem that people don’t need to solve. The algorithm itself was relatively straightforward, but the analysis to show that it would work seemed to be rather sophisticated.

Should the paper have been accepted? I argued for rejection:

• Most importantly, the paper was a solution looking for a problem. That’s not what we should be doing.
• The algorithm was essentially “standard in the literature” and looked like what I would have come up with on my first attempt.
• Sure, the proof that the algorithm would work in poly time looked tricky and involved some fancy math. But, so what?

That’s not to say that complexity has no place in AI. I’m a huge fan of using complexity results (and both hardness and approximation results can work fine here) to motivate heuristic solutions.

Anyway, I closed my part in the discussion with this:

In my ideal world this paper would be in SODA, not AAAI. It’s a “good paper” that “makes a contribution”, but that contribution isn’t to AI.

If we want AI to be something other than second-rate theory (and I’m actually not sure this paper isn’t “first-rate theory” but I’ll leave that to the theorists) then these are the kinds of papers we need to be rejecting at AI conferences.

It got in.