Summary and Contributions: - Complexity results on the weighted model integration - A new approach based on relaxing-compensating-recoverying idea from message passing in graphical models - Experiments showing the proposed approach achieves state-of-the-art performance
Strengths: - Solid work - Combination of theoretical and practical analysis of the problem - Sophisticated approach with SOTA performance - Good literature review
Weaknesses: - Motivation lacks a more direct connection with the problem at hand (how do we go from self-driving cars to integrating over intervals?) - Presentation require knowledgeable reader and relies heavily on supp. material - Experiments with artificial toy problems
Correctness: The theoretical results appear to be sound; the empirical methodology is correct.
Clarity: The paper is very dense, but the text is well-written. Some examples here and there could help introduce and engage the less knowledgeable reader.
Relation to Prior Work: The contributions are clearly presented, and related work is properly reviewed.
Reproducibility: Yes
Additional Feedback: In line 98, I believe Tb should take values in [0,1], not [-1,1].
Summary and Contributions: This paper focuses on the problem of weighted model integration. The paper has two components: theoretical hardness results and an abstraction based approach. The theoretical hardness claims that inference when tree width is 1 but diameter is n or when treewidth is 2 but diameter is log n is hard. The empirical part of the paper focuses on the rely, compensate and integrate approach which is similar to lot of work recently in counting community (see references below). The empirical results show promise.
Strengths: WMI is an important problem and the paper does attempt to make contributions along both angles. The empirical results clearly demonstrate progress over state of the art.
Weaknesses: There are two weaknesses with the paper: 1. I am not sure if the theoretical claims are correct. They seem very strong as only in propositional case, we have FPT for constant treewidth, so the claims need to talk about what makes problem so hard when you add in continuous variable. I looked at the proof and there are several things that trouble me: There is change of representation; subset sum is #P-complete when we are concerned with binary representation otherwise we have pseudo-polynomial time algorithms by dynamic programming. The proofs seem to work on integer representation not binary representation as the treewidth for binary representation is still n. The second issue is lack of relevant context to series of works on usage of abstraction to tackle the high treewidth case in the context of propositional formulas. I have listed references below. I think it is still okay for authors to claim that the prior work focuses on propositional case but their contribution focuses on the WMI. [1] Dell, H., Roth, M., Wellnitz, P.: Counting answers to existential questions. In: ICALP 2019. LIPIcs, vol. 132, pp. 113:1–113:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019) [2] Eiben, E., Ganian, R., Hamm, T., Kwon, O.: Measuring what matters: a hybrid approach to dynamic programming with treewidth. In: MFCS 2019. LIPIcs, vol. 138, pp. 42:1–42:15. Dagstuhl Publishing (2019) [3] Ganian, R., Ramanujan, M.S., Szeider, S.: Combining treewidth and backdoors for CSP. In: STACS 2017, pp. 36:1–36:17 (2017). https://doi.org/10.4230/LIPIcs.STACS.2017.36 [4] Hecher, M., Morak, M., Woltran, S.: Structural decompositions of epistemic logic programs. CoRR abs/2001.04219 (2020). http://arxiv.org/abs/2001.04219
Correctness: I am unsure about the correctness of theoretical results.
Clarity: The paper is well written on high level but since it makes a major claim, it should give intuition about the correctness of the proof.
Relation to Prior Work: Relevant references are missing as I have pointed above. It would be good if authors can add them so as to provide proper context to the reader.
Reproducibility: No
Additional Feedback: Thank you for the response. During the discussion phase, other reviewers clarified the reduction which makes me believe that the claim is probably correct. Since I have not been able to check details precisely, I think it is right from scientific perspective (given that these reviews would be public) for me to reserve full endorsement. I will strongly encourage authors to provide a rigorous proof of the claim; in the sense, clearly specifying the reduction from subset sum in binary representation to WMI in PTIME (taking care of the representation of the constraints). I have increased the score from 3 to 5 to reflect my opinion after the PC discussion.
Summary and Contributions: This paper presents theoretical and algorithmic results about the WMI framework. While the theoretical results are negative in the sense that they show the limits of the tractability of the problems solved by the WMI framework, the authors then present an algorithmic approach to overcome this limitation: an approximate WMI solver.
Strengths: Both theoretical and algorithmic results are very important for the concepts around WMI. The experimentation section if very clear and focus both on the questions answered by these experiences and the methods used.
Weaknesses: A minor issue that the Watts-Strogatz graphs are used in the experimentation section without any justification.
Correctness: To the best of my knowledge and understanding, I think that the claims of this paper are correct.
Clarity: Yes the paper is very well written. One typo in the conclusion: ourl -> our.
Relation to Prior Work: The relation to prior work is well defined.
Reproducibility: Yes
Additional Feedback: