Most of the reviewers were in favor of accepting. The main reservation expressed by the reviewers was that the assumptions of the theory are unrealistic, and so the theoretical contributions shouldn't be viewed as particularly significant in themselves. Specifically, the algorithm is motivated by some theory that is based on a conditional independence assumption that might not typically be satisfied. However, they showed (via a computational hardness result) that some kind of assumption is necessary for a solution to be tractable at all. So, since the resulting method seems reasonable and exhibits good empirical performance, the reviewers and I were mostly willing to look past this assumption.