Appeal to authority is only a fallacy when the person is an authority in an unrelated area. Appealing to an actual authority of the subject in question isn't a fallacy—it's the whole point of having authorities.
"90% of dentists agree you should own a motorbike" is an appeal to authority fallacy.
An appeal to authority is any logical argument that relies significantly upon the authority of the person making that argument as support for that argument. It then becomes circular and flawed.
If you were to replace the person who is actually speaking with anyone else, and look at the same argument and its support, and it doesn't hold up, that's an appeal to authority.
It doesn't matter who the authority is. Just that there was an authority used to support a significantly unsupported argument
> An argument from authority (argumentum ab auctoritate), also called an appeal to authority, or argumentum ad verecundiam, is a form of argument in which a claim made by an authority on some topic is used as evidence to support one's own claim.
Further down:
> Historically, opinion on the appeal to authority has been divided: some hold that it can be a valid or at least defeasible.
You seem to be arguing for appeals to authority as defeasible.
Incorrectly understanding the authority you are quoting shows how problematic it is to make pure appeals to authority.
Lol. But seriously appeal to authority fallacy need not be only when the authority is outside their domain. For instance when authority makes a bad argument.
The dividing line here is that it's fallacious to argue that something is true simply based on authority. That doesn't hold where there are external cogent reasons for following that authority (eg. in this example: it's a difficult problem that's well studied by many, and the body of work has not yet yeileded an answer such that it's unlikely that a more casual hunch will do so).
I'm not saying that this type of proof was applied perfectly here, however, the notion of proving that solving problem X must be hard because solving it would solve problem Y, which is (at least for now) known to be hard is a fundamental methodology in the field of computational complexity theory. There is a strong academic basis in these types of lines of reasoning, specifically in computing and optimization.
I'm not a trained computer scientist but didn't Daniel Lemire (purportedly) answer a different question from what OP asked? In OPs question k is fixed, wouldn't that open up avenues to implementation different from when k is not?
