[hvidgaard]

There is an impedance mismatch between the terminology in economics and CS. CS is at it's core a hard math discipline, and absolute statements are used a lot, and they differ quite a bit from what people outside of the field understand. This paper assumes a basic knowledge about CS theory and economic theory.

While you're right in your points here, the CS aspect of this paper leans on the CS theory. When a computer scientist say, "we cannot do this efficiently" it means, "We might be able to do this efficiently for some instances of the problem, but not for all instances". And when the scientist say "we can do this efficiently" it means "we know how to solve this in a way that when we double the input size, the difficulty will be a fixed factor larger. But it might be infeasible to solve any instance of the problem what so ever".