NeurIPS 2020

Probabilistic Inference with Algebraic Constraints: Theoretical Limits and Practical Approximations

Meta Review

Two reviewers rated the paper very highly (8, 9). R3 initially gave a very low rating and expressed concerns about correctness of the intractability result, especially related to the representation of numbers in the reduction from subset sum. This point received significant discussion. The meta-reviewer read the proof and felt it was very clear and agrees with the authors. There is one minor ambiguity that can be resolved: the authors don’t specify the representation of the constants that appear in the constraints in the WMI problem instance. It was assumed these should be rational numbers; in this case the constants constructed during the reduction for the constraints of the WMI problem have bit complexity proportional to that of the numbers that appear in the subset sum instance. Given that the only major critique was resolved during discussion, the meta-reviewer recommends accept. R3 expressed some hesitation, but raised their score from 3 to 5.