[JohnKemeny]

It means that you can choose constants such that the algorithm is as close to O(m) as you'd like.

In other words, it's an algorithm scheme that allows you to get an algorithm running in time O(m^ɛ) for any ɛ>1.

[Sniffnoy]

Sorry, where's that stated? I'm pretty doubtful of that claim because if that's what they meant they would say that -- they'd say it was O(m^(1+ɛ)), that would be well-understood notation. But what they wrote is that it's O(m^(1+o(1))), which, read as written, means it's a single bound that they're just not being very specific about.

I'm not asking for help decoding the notation; I'm asking for if anyone knows what the more detailed bound is that O(m^(1+o(1))) is abstracting.

[vitus]

That's because even the ACM link is an abbreviation of the actual paper.

Preprint at https://arxiv.org/abs/2203.00671

(Pages 68-75 build up the full details of the bound, which looks something like Õ(mκ⁻²α⁻²ϵ⁻¹). There are enough details over the preceding dozens of pages that I can't tell at a glance exactly what all the variables stand for.)

Technically this captures any logarithmic factors, such as exp(O(log^(7/8) m log log m)) as presented on page 75).