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

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

arxiv.org

Post reply on HN
Print view View original

31–40 of 44 posts

Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

#31

Post by theteapot »

esjeon wrote: post #10
onos wrote: post #2

Would love a tldr if anyone has a link.

I've just skimmed, but the paper is quite unkind about its internal details (which is very typical for mathies, hahaha). I think the algorithm is non-exact. Say, Theorem 1.1 explicitly mentions probability: > There is an algorithm that, on a graph G = (V, E) with m edges, vertex demands, edge costs, and upper/lower edge capacities, all integral and bounded by U in absolute value, computes an exact min-cost flow in m1…

> I've just skimmed, but the paper is quite unkind about its internal details (which is very typical for mathies, hahaha).

Excusing such only encourages it IMHO. I think it was Einstein who said "If you can't explain it to a six year old, you don't really understand it." Stupid "mathies".

Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

#32

Post by CaptainNegative »

adgjlsfhk1 wrote: post #27
CaptainNegative wrote: post #19

Earlier quoted context omitted.

(unless P=NP in which case all non-trivial problems in P are also NP-Complete)

I'm pretty sure this is false (unless you have a very odd definition of trivial).

Nothing funky. "Non-trivial" here is used in the same way as in Rice's theorem, i.e. the language is neither 0* (the program always returns false) nor 1* (the program always returns true).

It's ridiculously simple to show that if P=NP, then every nontrivial language A is NP-hard. For given a language B in NP, one can poly-time reduce B to A by writing a program to straight-up decide B in polynomial time, and then map true instances of B to a pre-determined true instance of A, and false instances of B to a pre-determined false instance of A. In particular, this means that any language in P is in both NP and NP-hard, and thus NP-complete.

Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

#33

Post by funcantor »

theteapot wrote: post #31
esjeon wrote: post #10

Earlier quoted context omitted.

I've just skimmed, but the paper is quite unkind about its internal details (which is very typical for mathies, hahaha). I think the algorithm is non-exact. Say, Theorem 1.1 explicitly mentions probability: > There is an algorithm that, on a graph G = (V, E) with m edges, vertex demands, edge costs, and upper/lower edge capacities, all integral and bounded by U in absolute value, computes an exact min-cost flow in m1…

> I've just skimmed, but the paper is quite unkind about its internal details (which is very typical for mathies, hahaha). Excusing such only encourages it IMHO. I think it was Einstein who said "If you can't explain it to a six year old, you don't really understand it." Stupid "mathies".

Its a research paper, the audience is going to be other experts in the field; it will be written in a way suitable for publishing to a journal. Even with a concise writing style, the paper is already at 100 pages. If you want to understand the paper it would make more sense to pick up a textbook and learn about the prerequisite material rather then expecting them to write a book for you, just to communicate their research result.

Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

#34

Post by theteapot »

funcantor wrote: post #33
theteapot wrote: post #31

Earlier quoted context omitted.

> I've just skimmed, but the paper is quite unkind about its internal details (which is very typical for mathies, hahaha). Excusing such only encourages it IMHO. I think it was Einstein who said "If you can't explain it to a six year old, you don't really understand it." Stupid "mathies".

Its a research paper, the audience is going to be other experts in the field; it will be written in a way suitable for publishing to a journal. Even with a concise writing style, the paper is already at 100 pages. If you want to understand the paper it would make more sense to pick up a textbook and learn about the prerequisite material rather then expecting them to write a book for you, just to communicate their res…

Explaining simply and rigorously are not mutually exclusive. They can do both.

Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

#35

Post by funcantor »

theteapot wrote: post #34
funcantor wrote: post #33

Earlier quoted context omitted.

Its a research paper, the audience is going to be other experts in the field; it will be written in a way suitable for publishing to a journal. Even with a concise writing style, the paper is already at 100 pages. If you want to understand the paper it would make more sense to pick up a textbook and learn about the prerequisite material rather then expecting them to write a book for you, just to communicate their res…

Explaining simply and rigorously are not mutually exclusive. They can do both.

I would agree with this, good explanations and rigour are definitely not mutually exclusive. But I am not sure what you are expecting. This is a research paper, intended to be read by other experts. Even still, if we look at how the paper is organised, the authors start with a high level overview, and build upon simpler problems to leverage their way to an understanding of the main result. For a research paper, it is extremely thorough.

If you want a 'simple explanation' that allows a layman to gain some understand the problem, sure. But this isn't, and absolutely should not be, the purpose or content of the research publication, which is to succinctly communicate to other experts the results of their findings.

Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

#36

Post by Ar-Curunir »

theteapot wrote: post #34
funcantor wrote: post #33

Earlier quoted context omitted.

Its a research paper, the audience is going to be other experts in the field; it will be written in a way suitable for publishing to a journal. Even with a concise writing style, the paper is already at 100 pages. If you want to understand the paper it would make more sense to pick up a textbook and learn about the prerequisite material rather then expecting them to write a book for you, just to communicate their res…

Explaining simply and rigorously are not mutually exclusive. They can do both.

simple != simple for laymen. It doesn’t make sense to recap the entire history of a field in the intro

Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

#38

Post by adgjlsfhk1 »

CaptainNegative wrote: post #32
adgjlsfhk1 wrote: post #27

Earlier quoted context omitted.

I'm pretty sure this is false (unless you have a very odd definition of trivial).

Nothing funky. "Non-trivial" here is used in the same way as in Rice's theorem, i.e. the language is neither 0* (the program always returns false) nor 1* (the program always returns true). It's ridiculously simple to show that if P=NP, then every nontrivial language A is NP-hard. For given a language B in NP, one can poly-time reduce B to A by writing a program to straight-up decide B in polynomial time, and then map…

Oops. I'm used to thinking of polynomial reductions as "cheap reductions" which given hindsight is obviously misleading when P=NP.

Re: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

#40

Post by okintheory »

SeanLuke wrote: post #39

What does $m^{1 + O(1)}$ time mean exactly? This could be m^5000 for all we knew. How is this almost-linear, and how can it be guaranteed?

It's little-oh, not Big-Oh (o(1) is not O(1)). Instead $f(n) = o(1)$ means $\lim_{n \to infty f(n)} = 0$. So $m^{1+o(1)}$ is smaller than $m^1.00001$ for large enough m.
Post reply on HN