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 work complexity O(m^3n^3\log mn).