I 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.
Got it! Thanks!