4 ms·

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 g

• Sniffnoy 2y ago
  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 2y ago
    That's because even the ACM link is an abbreviation of the actual paper. Preprint at https://arxiv.org/abs/2203.00671 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).