Before revision:  Achieving this running time requires proving several new structural properties of the MAP.
After revision:  Achieving this running time requires proving several structural properties of the MAP.