I see a lot of buzzwords (applications of the algorithm that are just applications of anything) and little description about the actual details of the algorithm, complexity theory, and what type of problems it solves, obviously assuming they didn't turn NP into P.
New research a ‘breakthrough for large-scale discrete optimization’
11–20 of 21 posts
Re: New research a ‘breakthrough for large-scale discrete optimization’
#12I skimmed through because it sounds fairly click-baity... From what I gather, they're claiming to have solved NP-complete problems to some degree with some abstract form algorithm? I'm genuinely interested, if anyone can explain what's going on...
The article doesn't even mention NP-completeness. Nor does the paper: https://arxiv.org/pdf/1804.06355.pdf
Haven't read enough yet to comment otherwise, but let's not spread rumours.
Re: New research a ‘breakthrough for large-scale discrete optimization’
#13I skimmed through because it sounds fairly click-baity... From what I gather, they're claiming to have solved NP-complete problems to some degree with some abstract form algorithm? I'm genuinely interested, if anyone can explain what's going on...
The abstract seems to be comparing having to search an entire problem space for the most optimal result ("the current approach") with an approach using sampling for a good enough result?
Re: New research a ‘breakthrough for large-scale discrete optimization’
#14Title could also be "Researchers find a better heuristic for a class of exponentially scaling problems."
There's no claim to have changed the complexity class, so"exponentially faster" just means the problem is still exponentially in problem size, but the exponent is smaller.
From the looks of it, though, it is a nice result because it has pretty wide applicability.
Re: New research a ‘breakthrough for large-scale discrete optimization’
#15Title could also be "Researchers find a better heuristic for a class of exponentially scaling problems." There's no claim to have changed the complexity class, so"exponentially faster" just means the problem is still exponentially in problem size, but the exponent is smaller. From the looks of it, though, it is a nice result because it has pretty wide applicability.
No, "exponentially faster" means exponentially faster with exponentially more hardware. Specifically, N processors can solve a problem of size N in O(log N) wall clock time, where the previous (serial) algorithm used O(N) wall clock time. Most programmers would say "more scalable" or "more parallel" rather than "faster", but the terminology makes sense and is standard in the context of the PRAM model of parallel computation.
I'm not sure, but I doubt this algorithm is "faster" than the previous one on a single processor.
(The article is drivel; I couldn't figure out what they were talking about either, until I looked at the paper)
Re: New research a ‘breakthrough for large-scale discrete optimization’
#16"What if a large class of algorithms used today -- from the algorithms that help us avoid traffic to the algorithms that identify new drug molecules -- worked exponentially faster?" -- these problems used as example in the opening line are only tangentially related to the problem of submodular maximisation that the paper it is talking about is tackling. I also don't think submodular maximisation is widely used today for identifying new drug molecules or avoiding traffic.
Re: New research a ‘breakthrough for large-scale discrete optimization’
#17Title could also be "Researchers find a better heuristic for a class of exponentially scaling problems." There's no claim to have changed the complexity class, so"exponentially faster" just means the problem is still exponentially in problem size, but the exponent is smaller. From the looks of it, though, it is a nice result because it has pretty wide applicability.
No, "exponentially faster" means exponentially faster with exponentially more hardware . Specifically, N processors can solve a problem of size N in O(log N) wall clock time, where the previous (serial) algorithm used O(N) wall clock time. Most programmers would say "more scalable" or "more parallel" rather than "faster", but the terminology makes sense and is standard in the context of the PRAM model of parallel com…
Ah ok, yeah TBH I didn't read the article, but was guessing from the headline this is what they meant since in exponentially scaling problems theres always room at the top (unless explicitly proven otherwise).
Re: New research a ‘breakthrough for large-scale discrete optimization’
#18I skimmed through because it sounds fairly click-baity... From what I gather, they're claiming to have solved NP-complete problems to some degree with some abstract form algorithm? I'm genuinely interested, if anyone can explain what's going on...
Submodular maximization is indeed NP-complete, but we can find approximate solutions in polynomial time. This paper speeds up the parallel running time of the approximation from O(n) to O(log n), meaning that they've found a way to make the algorithm more parallelizable, though you still have to do the same amount of work.
Re: New research a ‘breakthrough for large-scale discrete optimization’
#19I've seen two recent posts that mention 'exponentially faster '. Does this have a precise meaning? I could imagine it to mean making a non-exponential algorithm for a problem which only had exponential ones. Another interpretation could be making an algorithm with 2^n steps where previous ones took 2^(2n) steps making the improvement factor 2^n, but still resulting in an exponential time algorithm. Should we just acc…
In this case, exponentially faster means that the parallel running time improved from O(n) to O(log n).
Re: New research a ‘breakthrough for large-scale discrete optimization’
#20Could this (maybe only slightly) push out how long before quantum computers pass traditional?