Before revision:  The problem exhibits a typical information-to-computational-gap observed in analogous settings, that widens with increasing sparsity of the problem.
After revision:  The problem exhibits a typical information-to-computational-gap observed in analogous sparse settings that widen with increasing sparsity of the problem.