Paper ID: 1028
Title: Beyond Parity Constraints: Fourier Analysis of Hash Functions for Inference

Review #1
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): The authors consider the problem of approximating large sums occurring for example in discrete integration. They study hashing functions that are more efficient to compute than parity constraints. They relate the Fourier specturm of boollean functions to the variance of hashing families and generalise the result of Ermon et al. relating clash probabilities and noise sensitivity in the case of short XORs to a more general family of hashing functions. They propose two new hashing functions which they validate on discrete integration and model counting problems by adapting the WISH algorithm proposed by Ermon et al. (2013).

Clarity - Justification: The paper is well written, clearly defining the problem statement and introducing the background material. The theoretical results and extensions are also described appropriately. However, the exposition becomes less accessible when turning to their actual application. For example, it was not clear to me how the results in Section were useful to derive MAJORITY and TRIBES. It was unclear to me how Figure 1 was obtained and how this related to hash function correlations. WISH (and how it differs to the proposed modified version) would deserve to be explained into more detail as all results are obtained by adapting it to the new hashing functions.

Significance - Justification: The problem of discrete integration is an important problem in Bayesian inference. The relation between the Fourier spectrum and the variance of hash function families seems to be novel, as well as Theorem 1 hash families. The proposed hashing function families, TRIBES and MAJORITY, respectively suitable for model counting and discrete integration were demonstrated to perform well in practice, significantly improving runtimes over competing approaches. I was wondering how the results vary, for example, when running experiments on problems of increasing size? Also, am I reading Figure 2 correctly: mean field is outperforming MAJORITY WISH? If this is the case it would deserve a discussion.

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): - The Fourier spectrum is never formally defined in the paper. - In Theorem 2, where does the 0.0042 come from? 

=====

Review #2
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): The paper continues a recent line of works (particularly by Ermon et al.), which reduce weighted integration (counting) to constrained optimization. Previous instantiations of the approach have been based on random parity constraints, which tend to yield hard instances of the optimization problem. The present work introduces a richer, Fourier analysis based framework, which allows a controlled way to discover other classes of constraints, in particular ones yielding significantly easier optimization problem instances. As examples, the paper gives and studies so-called tribes and majority constraints. The statistical properties of these classes are strong enough to offer good high-probability lower-bounds, but too weak to offer respective upper bounds (unlike parity constraints). Experimental results suggest that the example classes indeed yield much easier optimization tasks, while keeping accurate estimates.

Clarity - Justification: The paper is well written and surprisingly easy to read given the technically challenging material. I was able to spot only a few typos, like alpha_i in place of epsilon_i in Prop.3 on line 508.  Also, in Fig.1, should state clearly that n=10 if that is the case. In addition, I'd recommend using proper punctuation also in displayed equations, even if this is not critical for clarity. 

Significance - Justification: This is a high-quality work that seems to truly advance our understanding of the hash-and-optimize approach to approximate counting. It is a pity that the derived "new" classes of constraints do not yield useful high-probability upper bounds: namely, it is precisely upper bounds that are hard to get; lower bounds are much easier in general. 

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): Line 821: "3-4" -> "3--4" Line 865: "1-2" -> "1--2 Line 871: "''templates''" -> "``templates''"  Polish the reference list (consistently either initials or full first name for all authors, capitalize monte carlo, etc.). 

=====

Review #3
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): The focus of the paper is computing discrete sums sum_{x in S} w(x) where S is a subset of {0,1}^n and w(x)>=0.  One category of approaches to this involves sampling hash functions, hashing inputs, and considering the intersection of the domain S and inverse hash. The intersection should be concentrated about its mean; it is common to use eps-AU hash families which can be implemented using LDPC codes. The paper proposes a general framework for analyzing statistical properties of hash functions in terms of their Fourier spectrum. The spectrum is closely tied to noise sensitivity of a function, and functions with certain noise sensitivity properties are shown to be (eps,q)-AU (where eps depends on the function). Hence noise sensitivity can be used to assess / design new hash functions. The authors propose using two new types of functions, called TRIBES and MAJORITY, which can be more compact than LDPC. They use a modification of the WISH algorithm with their hash functions to compute discrete summations. Their method outperforms others on the tasks of computing the MRF partition function and estimating the solution size of CNF formulas.

Clarity - Justification: The paper is dense but clearly written, and provides relevant background. It could be improved by keeping notation consistent throughout. For example S refers to different types of sets in 2.1 and 2.2, and sigma(x_i) notation in line 342 is confusing. 

Significance - Justification: The approach is novel and non-trivial, and seems useful in practice. I'm not familiar enough with the area to judge significance.

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): No other comments

=====