Hacker News new | ask | show | jobs
by Sniffnoy 719 days ago
The abstract just says the time is m^(1+o(1))... anyone know if a more specific bound is stated anywhere?
3 comments

Note that this is a „small o“, so o(1) captures terms that „divided by 1“ go to zero as m to infinity.

https://de.m.wikipedia.org/wiki/Landau-Symbole

English Wikipedia has an explanation, too: https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notati...
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.

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.

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

That is the specific bound. The little o is a function that aproaches 0 as n approaches infinity, referred to as asymptotically negligible.
I know what the notation means. I'm wondering what the actual function is. Using little o is a way of abstracting that information away.
I could be wrong but I think many times the researchers don't care about the exact function. It could be something like 1/log(log(n)) .
Yes, I am very aware that many times they don't, but that doesn't mean they shouldn't!

Fortunately, in many cases, even when the detail is omitted from the headline theorem, they did in fact do the work and it is in fact stated lower down in the body of the paper; or in other cases they fail to state it but it can be easily assembled from a few parts. That's why I was asking.

But sometimes though it's a big complicated thing and they were just like, eh, let's not bother figuring out exactly what it is. To which I say, laziness! You're just making other people do a proof-mine later! You're doing this much, do the work to get a concrete bound, because you can do it better than later proof-miners can!

I won't say that in an ideally functioning mathematics proof-mining would never be necessary, that'd be like saying that in a well-written mathematics one would never need to refactor, but c'mon, mathematicians should at least do what they can to reduce the necessity of it.