I spent some (too many) months looking into this domain so I can maybe give some context.
The astonishing improvement here is that we can compute exact flows in almost-linear time. Previous algorithms for computing almost-optimal flows in almost-linear time have been known for some time, and hence it was expected that someone would eventually find an algorithm that finds optimal flows in almost-linear time. Well, looks like it's finally here!
I've only skimmed the paper but it seems to me that the authors draw on a set of techniques established for the almost-optimal case. These come with rather enormous constants, so it is unlikely that there will be a practical implementation of this algorithm any time soon.
I am going to ask a question from a very naive POV, 5 yo:
ELI5 the following please ;
---
Given that "enormous constants" are required (i.e. huge lee-way) in the source of inputs (if thats worded correctly), Would it be perceivable, that in future, we may feed such zygote algorithms to some other AI/ML/Algo/Whatever, such that it churns through implementation scenarios quickly to refine it to a practical tool?
I don't think the problem is that we can't develop a practical implementation, it's that the constant being hidden by the asymptotic notation is inherently huge, making the algorithm impractical given the input sizes we are interested in.
There are a lot of problems where this shows up, notably testing primality (we can do that in poly time but it's O(n^6) or something iirc) and matrix multiplication (Strassen's algo).
At what point are we looking at the inter-relationships and commonalities among all practical implementations which share common input [groups, types, {trait}], etc...
,, Our framework extends to an algorithm running in m1+o(1) time for computing flows that minimize general edge-separable convex functions to high accuracy.''
This looks like an interesting improvement possibility over the current algorithm for optimal pathfinding over the Lightning Network by Rene Pickhart, it would be interesting to know what he thinks about it:
It's so amusing how interviewers pose questions that took PhD students years to invent the answers to. Just say you want me to memorize some algorithms and their time+space complexities, and regurgitate them on command.
> It's so amusing how interviewers pose questions that took PhD students years to invent the answers to.
That doesn't really mean anything without additional context... like what the questions you're talking about were, or what the positions were, or what you claimed about your background, approximately how long ago said PhDs were earned, or what the interviewers actually expected from you (which may not have been the final solution at all), or... etc.
So much of what we learn, use, and understand was developed by people far more talented than us. Literally everything from algebra to binary digital logic. It should be obvious that something can be orders of magnitude more difficult to come up with the first time, when you have nobody to learn it from, and when the rest of the world is far behind where the field is, than it might be to come up with it when the entire world has advanced and you've (presumably) been taught extremely relevant material & perspective in a nice and polished classroom setting. Now, obviously, it can also be just as difficult in the second case as in the first case for some problems too. It depends entirely on the problem and context.
Some do. Other companies expect you to derive the algorithm from scratch if you haven't seen that one. If you don't know the algorithm, then question is over. It's unreasonable to expect someone to derive in 10 minutes something that took years to invent.
That’s not what I’m looking for in those kinds of interviews. For example, one of my fav problems has a Range Sum Query tree idea as the main solution. But I’m more than happy to lead any developer to the solution, they come away happy with new knowledge, I see how they respond to hints and think on a new problem. Always fun and heard a lot of direct thanks for that from interviewees.
Does anyone know if these algorithms are practical on real problems on real machines, or is the constant term large enough you would normally just use a more traditional algorithm for most work?
The constants are enormous enough that you'd never want to use these algorithms in practice - for now, at least. There's a key problem that uf resolved would allow quite efficient implementations of this family of algorithms even on the GPU, something that previously wasn't really possible for such graph algorithms.
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.
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.
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.
> 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.
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.
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.
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.
The astonishing improvement here is that we can compute exact flows in almost-linear time. Previous algorithms for computing almost-optimal flows in almost-linear time have been known for some time, and hence it was expected that someone would eventually find an algorithm that finds optimal flows in almost-linear time. Well, looks like it's finally here!
I've only skimmed the paper but it seems to me that the authors draw on a set of techniques established for the almost-optimal case. These come with rather enormous constants, so it is unlikely that there will be a practical implementation of this algorithm any time soon.