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?