undefined | Better HN

0 pointsSniffnoy1y ago0 comments

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.

0 comments

vitus1y ago

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).

j / k navigate · click thread line to collapse