Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Researchers achieve ‘absurdly fast’ algorithm for network flow

quantamagazine.org

Post reply on HN
Print view View original

71–80 of 80 posts

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#71

Post by doctorhandshake »

paulpauper wrote: post #24
antegamisou wrote: post #11

Earlier quoted context omitted.

I'd agree with you ~1 year ago but I think a lot of their articles now tend to water-down lots of complex subjects in rigorous math papers. Still remains one of my favorite websites.

i think they have to water it down so much because hardly anyone would understand the math, even people who consider themselves good at math or have degrees in STEM..it's just so advanced even relative to that .

Yeah this is me. No advanced STEM background so just barely hanging on by a thread. I enjoy being immersed in topics I don’t understand but I get more out of it with a little something to hang on to.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#72

Post by gauddasa »

The best known algorithms, say relabel-to-front, is O(m^1.5) and the paper proposes an algorithm which is O(m^(1+o(1)). Here, 1.5 is fixed but 1+o(1) can be anywhere between 1 and 2 based on your luck, and should be 1.5 on an average over variety of inputs. Still no free lunch.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#75

Post by account42 »

themonteray wrote: post #21
titanomachy wrote: post #20

Earlier quoted context omitted.

I've been out of school for a while, what does m^(1+o(1)) mean? Isn't any constant trivially in "o(1)"? So m^1000 is in this class? Or are they using it informally to mean "a very small number"?

o(1) is "little O" notation, where for a function y = o(f), y(x) / f(x) --> 0 as x --> infinity. In other words, y goes to 0 faster than f. In this context, m^(1 + o(1)) means roughly that you converge to linear time for large m.

I wish we could all collectively agree that using = for the o/O/etc. notations is stupid and stop this. These are sets of functions. f is not equal to the set, it is an element of the set and we already have a well defined notation for that: f ∈ o(...). So use that or use the LateX f \in o(...) if you want to restrict yourself to ASCII. Using = only serves to confuse.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#76

Post by nephanth »

gauddasa wrote: post #72

The best known algorithms, say relabel-to-front, is O(m^1.5) and the paper proposes an algorithm which is O(m^(1+o(1)). Here, 1.5 is fixed but 1+o(1) can be anywhere between 1 and 2 based on your luck, and should be 1.5 on an average over variety of inputs. Still no free lunch.

> based on your luck

Uh, no, based on the size of your input. o(1) means something that goes to 0 as m gets bigger, it has nothing to do with randomness.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#77

Post by gauddasa »

nephanth wrote: post #76
gauddasa wrote: post #72

The best known algorithms, say relabel-to-front, is O(m^1.5) and the paper proposes an algorithm which is O(m^(1+o(1)). Here, 1.5 is fixed but 1+o(1) can be anywhere between 1 and 2 based on your luck, and should be 1.5 on an average over variety of inputs. Still no free lunch.

> based on your luck Uh, no, based on the size of your input. o(1) means something that goes to 0 as m gets bigger, it has nothing to do with randomness.

I deliberately wrote "variety of inputs" to already clarify that a single input is a random sample from its underlying distribution.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#78

Post by gauddasa »

gauddasa wrote: post #77
nephanth wrote: post #76

Earlier quoted context omitted.

> based on your luck Uh, no, based on the size of your input. o(1) means something that goes to 0 as m gets bigger, it has nothing to do with randomness.

I deliberately wrote "variety of inputs" to already clarify that a single input is a random sample from its underlying distribution.

No post body was provided.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#79

Post by miclill »

atorodius wrote: post #45
nothrowaways wrote: post #43

Link to the paper https://arxiv.org/abs/2203.00671

Is it common in this field to have 100 page „papers“? Just curious

> The team’s analysis is long and complicated, but other researchers will soon dive in to simplify things, Rao predicted.

Re: Researchers achieve ‘absurdly fast’ algorithm for network flow

#80

Post by pvillano »

account42 wrote: post #75
themonteray wrote: post #21

Earlier quoted context omitted.

o(1) is "little O" notation, where for a function y = o(f), y(x) / f(x) --> 0 as x --> infinity. In other words, y goes to 0 faster than f. In this context, m^(1 + o(1)) means roughly that you converge to linear time for large m.

I wish we could all collectively agree that using = for the o/O/etc. notations is stupid and stop this. These are sets of functions. f is not equal to the set, it is an element of the set and we already have a well defined notation for that: f ∈ o(...). So use that or use the LateX f \in o(...) if you want to restrict yourself to ASCII. Using = only serves to confuse.

(some descriptive linguistics) People often think of "=" as "is", when "is" can convey both equality and possession of an attribute. IIRC there was an article about how American kids think "=" means "the answer is" because they first encountered it with equations like 5+5=10. I've also seen people write 2x+5=10 = 2.5, meaning "the answer to the problem 2x+5=10 is 2.5"
Post reply on HN