[esjeon]

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+o(1) log2 U time with high probability.

(See how their "theorem" is much easier to understand than the abstract...)

This is a kind of advanced algorithm with a sprinkle of optimization, so normal dudes won't be able to get a grasp on this easily. Also, this is too much for my caffeinated Monday morning.

[xyzzyz]

The algorithm is exact, but probabilistic. That means that if you repeat it enough times, you're almost certain to find a solution.

Here's an example of how that works. Suppose you have a polynomial f(x) of degree n. I'll show a probabilistic algorithm that'll find an integer k such that f(k) != 0 with probability p >= 1/2.

Here goes: pick a random non-negative integer k below 2n. That's it, that's our answer.

What's the probability that f(k) != 0? Well, a polynomial of degree n can have at most n zeros, so at most n out of 2n non-negative integers below 2n are bad answers, so the probability of k being bad (i.e. f(k) = 0) is <= 1/2. Thus, probability of getting a correct answer is >= 1/2.

Now, probability 1/2 might seem pretty bad, we're, after all, rather likely to get a wrong answer. There's a simple way to deal with it, though: just repeat the algorithm as many times as you need. For example, if we repeat the algorithm 10 times, the probability of getting 10 wrong answers is 1/2^10 = 1/1024, rather small indeed. After 100 times, the probability of getting wrong answer is negligible.

Of course, it's easy to come up with an exact, non-probabilistic algorithm for the problem above. However, my probabilistic algorithm is O(1), while it's easy enough to prove that no constant time, non-probabilistic algorithm for the problem exists. I imagine that the situation is similar with the algorithm in the paper above: I'd wager that we get almost-linear time thanks to probabilistic nature.

Oh, and I was also cheating above somewhat: sure, my algorithm is O(1), but verifying that the answer is actually correct is O(n), so I cannot get an arbitrary small probability with my algorithm using the method above in constant time. The situation is, however, better in the context of maximum flow problem, because one can, in fact, check whether a flow is maximum in linear time, so that we can amplify the probability of getting a correct answer without losing the linear complexity.

[theteapot]

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

[funcantor]

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.

[theteapot]

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

[funcantor]

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.

[Ar-Curunir]

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

[marcosdumay]

It's hard enough to create the thing and make your explanation fit on the page limit. You also want people to make it comprehensible at the same time?

If you want to, you can study it, make it easier to understand and write another paper. If it's good, you will do both yourself and the original author a huge favor.