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 statistical-to-computational gap observed in analogous settings, that widens with increasing sparsity of the problem.