Before revision:  The previous best known parallel predicate detection algorithm, ParallelCut, had work complexity O(m^3n^3\log mn).
After revision:  The previous best known parallel predicate detection algorithm, ParallelCut, had, has time complexity O(\log mn) and work complexity O(m^3n^3\log mn).