{'fraction_non_alphanumeric': 0.03906732049491768, 'fraction_numerical': 0.011041470464066509, 'mean_word_length': 4.5625, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimization With Parity Constraints: From Binary Codes to Discrete Integration

Many probabilistic inference tasks involve summations over exponentially large sets. Recently, it has been shown that these problems can be reduced to solving a polynomial number of MAP inference queries for a model augmented with randomly generated parity constraints. By exploiting a connection with max-likelihood decoding of binary codes, we show that these optimizations are computationally hard. Inspired by iterative message passing decoding algorithms, we propose an Integer Linear Programming (ILP) formulation for the problem, enhanced with new sparsification techniques to improve decoding performance. By solving the ILP through a sequence of LP relaxations, we get both lower and upper bounds on the partition function, which hold with high probability and are much tighter than those obtained with variational methods.


INTRODUCTION
Discrete probabilistic graphical models [18,31] are often defined up to a normalization factor involving a summation over an exponentially large combinatorial space. Computing these factors is an important problem, as they are needed, for instance, to evaluate the probability of evidence, rank two alternative models, and learn parameters from data. Unfortunately, computing these discrete integrals exactly in very high dimensional spaces quickly becomes intractable, and approximation techniques are often needed. Among them, sampling and variational methods are the most popular approaches. Variational inference problems are typically solved using message passing techniques, * This work was supported by NSF Grant 0832782.
which are often guaranteed to converge to some local minimum [30,31], but without guarantees on the quality of the solution found. Markov Chain Monte Carlo [17,21,32] and Importance Sampling techniques [10,11,13] are asymptotically correct, but the number of samples required to obtain a statistically reliable estimate can grow exponentially in the worst case.
Recently, Ermon et al. [6] introduced a new technique called WISH which comes with provable (probabilistic) guarantees on the approximation error. Their method combines combinatorial optimization techniques with the use of universal hash functions to uniformly partition a large combinatorial space, originally introduced by Valiant and Vazirani to study the Unique Satisfiability problem and later exploited by Gomes et al. [13,14] for solution counting. Specifically, they show that one can obtain the intractable normalization constant (partition function) of a graphical model within any desired degree of accuracy, by solving a polynomial number of MAP queries for the original graphical model augmented with randomly generated parity constraints as evidence. Although MAP inference is NP-hard and thus also intractable, this is a significant step forward as counting problems such as estimating the partition function are #-P hard, a complexity class believed to be significantly harder than NP.
In this work, we investigate the class of MAP inference queries with random parity constraints arising from the WISH scheme. These optimization problems turn out to be intimately connected with the fundamental problem of maximum likelihood decoding of a binary code [3,29]. We leverage this connection to show that the inference queries generated by WISH are NP-hard to solve and to approximate, even for very simple graphical models. Although generally hard in the worst case, message passing and related linear programming techniques [7] are known to be very successful in practice in decoding certain types of codes such as low density parity check (LDPC) codes [8].
Inspired by the success of these methods, we formulate the MAP inference queries generated by WISH as Integer Linear Programs (ILP). Unfortunately, such queries are typically harder than traditional decoding problems because they involve more complex probabilistic models, and because universal hash functions naturally give rise to very "dense" parity constraints. To address this issue, we propose a technique to construct equivalent but sparser (and empirically easier to solve) parity constraints. Further, we introduce a more general version of WISH that relies directly on arbitrarily sparse parity constraints, thus giving rise to easier to solve MAP queries but providing weaker, one-sided guarantees on the approximation error for the partition function.
Our ILP formulation with sparsification techniques provides very good lower bounds on the partition function, while at the same time providing also upper bounds based on solving a sequence of LP relaxations. These upper bounds are much tighter than those obtained by tree decomposition and convexity [30]. This is a significant advance, because other state-of-the-art sampling based algorithms [10,11,13,32] can usually provide probabilistic guarantees on lower bounds, but are not able to reason at all about upper bounds.

PROBLEM STATEMENT
We consider a discrete probabilistic graphical model [31] with n = |V | random variables {x i , i ∈ V } where each random variable x i takes values in a finite set X i . We consider a factor graph representation for a joint probability distribution over elements x ∈ X = X 1 × · · · × X n (also referred to as configurations) This is a compact representation for p(x), which is defined as the product of non-negative factors ψ α : {x} α → R + , where I is an index set and {x} α ⊆ V a subset of variables the factor ψ α depends on. Z is a normalization constant known as partition function ensuring the probabilities sum up to one. Formally the partition function Z is defined as where for compactness we have introduced a weight function w : X → R + that assigns to each configuration x ∈ X its unnormalized probability, namely Computing the partition function Z is a #-P complete, intractable problem because it involves a sum over an exponentially large number of configurations. However, the partition function is a key property of a graphical model, needed e.g. to actually evaluate the probability of a configuration x under p. In this paper, we will focus on approximate techniques to estimate and bound this quantity. For simplicity, we consider the case of binary variables where x i ∈ X i = {0, 1}. The general case can be encoded using a bit representation and binary variables.

BACKGROUND
This paper extends previous work by Ermon et al. [6] who introduced an algorithm called WISH to estimate the partition function (2). WISH is a randomized approximation algorithm that gives a constant factor approximation of Z with high probability. It involves solving a polynomial number of MAP inference queries for the graphical model conditioned on randomly generated evidence based on universal hashing.

FAMILIES OF HASH FUNCTIONS
A key ingredient of the WISH algorithm is the concept of pairwise independent hashing, originally introduced by Carter and Wegman [5] and later recognized as a tool that "should belong to the bag of tricks of every computer scientist" [33]. There are several indepth expositions of the topic [cf. 12,27,28]. Here we will also make use of a weaker notion of hashing, called uniform hashing and defined as follows: The basic idea behind WISH is to (implicitly) randomly partition the space of all possible configurations by universally hashing configurations into 2 m buckets. This step is achieved using randomly generated parity constraints of the form Ax = b mod 2, which may also be viewed as logical XOR operations acting on the binary variables of the problem: A combinatorial optimization solver is then used to find a configuration with the largest weight within a single bucket. This corresponds to solving a MAP query, i.e., solving an optimization problem subject to (randomly generated) parity constraints. By varying the number of buckets and repeating the process a small number of times, this strategy provably yields an estimate of the intractable normalization factor (2) within any desired degree of accuracy, with high probability and using only a polynomial number of MAP queries. For completeness, we provide the pseudocode for WISH as Algorithm 1, modified to have the hash families H n,i , i ∈ {0, 1, . . . , n}, as parameters whose variations we will consider later 1 . We will write WISH({H n,i }) when the values of the other parameters are implicit.
Although MAP inference itself is an NP-hard problem, this strategy is still desirable considering that computing Z is a #P-hard problem, a complexity class believed to be even harder than NP. In practice, Ermon et al. [6] showed that the resulting MAP inference can be solved reasonably well using a state-of-the-art MAP inference engine called Toulbar [1], which was extended with custom propagators for parity constraints. Further, even if the MAP instances in the inner loop of Algorithm 1 are not solved to optimality, the output of the algorithm using suboptimal MAP solutions is an approximate lower bound for Z (specifically, no more than 16Z) with probability at least (1 − δ). If suboptimal solutions are within a constant factor L of the optimal, then the output is a 16L-approximation of Z with probability at least (1−δ) [6]. Similarly, if one has access to upper bounds to the values of the MAP instances, the output of the algorithm using these upper bounds is an approximate upper bound (specifically, at least 1/16Z) for Z with probability at least (1 − δ).

IMPROVING WISH: HASHING USING TOEPLITZ MATRIX
The performance of Algorithm 1 can be improved by constructing pairwise independent hash functions not by choosing A ∈ R {0, 1} i×n but rather letting A be a random i × n Toeplitz matrix [24]. Specifically, the first column and row of A are filled with uniform i.i.d.
Bernoulli variables in {0, 1}. The value of each entry is then copied into the corresponding descending topleft to bottom-right diagonal. This process requires n + i − 1 random bits rather than ni = O(n 2 ). Let T (m, n) ⊆ {0, 1} m×n be the set of m × n Toeplitz matrices with 0, 1 entries. Then:

WISH({H n,m
T }) still provides the same theoretical guarantees as Theorem 1 but has a more deterministic and stable behavior as it requires only Θ(n 2 log n) random bits rather than Θ(n 3 log n).
To shed some light on this question, we show a connection with a decision problem arising in coding theory: . Given a binary m × n matrix A, a vector b ∈ {0, 1} m , and an integer w > 0, is there a vector z ∈ {0, 1} n of Hamming weight ≤ w, such that Az = b mod 2?
As noted by Vardy [29], Berlekamp et al. [3] showed that this problem is NP-complete with a reduction from 3-DIMENSIONAL MATCHING. Further, Stern [26] and Arora et al. [2] proved that even approximating within any constant factor the solution to this problem is NP-hard.
These hardness results restrict the kind of problems we can hope to solve in our setting, which is more general. In fact, we can define a graphical model with single variable factors where H(x) is the Hamming weight of x. Thus, MAXIMUM-LIKELIHOOD DECODING of a binary code is a special case of MAP inference subject to parity constraints, but on a simple (disconnected) factor graph with factors acting only on single variable nodes. Intuitively, in the context of coding theory, there is a variable for each transmitted bit, and factors capture the probability of a transmission error on each bit. Thus there are no interactions between the variables, except for the ones introduced by the parity constraints Ax = b mod 2, while in our context we allow for more complex probabilistic dependencies between variables specified as in Eq. (1). We therefore have the following theorem: Theorem 2. Given a binary m×n matrix A, a vector b ∈ {0, 1} m , and w(x) as in Equation (3), the following optimization problem is NP-hard to solve and to approximate within any constant factor.
Connections with coding theory is even deeper, and is not just an artifact of the particular hash function construction used. In fact, there is an intimate connection and a correspondence between universal hash functions and (binary) codes, where one can construct hash functions from binary codes and vice versa [27].

MESSAGE PASSING DECODING
Iterative Message Passing (MP) methods are among the most widely used decoding techniques. Although the decoding problem is computationally intractable, they usually have very good performance in practice [7,19]. Since we can represent parity constraints as additional factors in our original factor graph model, MP techniques can also be heuristically applied to solve the more general MAP inference queries with parity constraints generated by WISH. Specifically, although a parity constraint over k variables would require a conditional probability table (CPT) of size 2 k to be specified, efficient Dynamic-Programming-based updates for parity constraints are known, see e.g. [19]. These updates have complexity which is linear in k, and thus, by representing parity constraints implicitly, we can directly use these techniques.

INTEGER PROGRAMMING FORMULATION
The NP-hard combinatorial optimization problem max σ w(σ) subject to Aσ = b mod 2 can be formulated as an Integer Program [4]. This is a promising approach because Integer Linear Programs and related Linear programming (LP) relaxations have been shown to be a very effective at decoding binary codes by Feldman et al. [7]. Further, the empirically successful iterative message-passing decoding algorithms are closely related to LP relaxations of certain Integer Programs, either because they are directly trying to solve an LP or its dual like the MPLP and TRWBP [9,25,30], or attempting to approximately solve a variational problem over the same polytope like Loopy Belief Propagation [31].

MAP INFERENCE AS AN ILP
For simplicity, we consider the case of binary factors (pairwise interactions between variables), where equation (3) for some edge set E. Rewriting in terms of the logarithms, the unconstrained MAP inference problem can be stated as max x∈{0,1} n i∈V θ i (x i ) + (i,j)∈E θ ij (x i , x j ) which can be written as an Integer Linear Program using binary indicator variables {µ i , i ∈ V } and {µ ij (x i , x j ), (i, j) ∈ E, x i ∈ {0, 1}, x j ∈ {0, 1}} as follows [31]: max µi,µij (xi,xj ) i∈V µi,j(xi, 1) = µj

PARITY CONSTRAINTS
There are several possible encodings for the parity constraints Aσ = b mod 2, defining the so called parity polytope over σ ∈ R n . We summarize them next. Let J be the set of parity constraints (one entry per row of A). Let N (j) be the set of variables the jth parity constraint depends on, namely the indexes of the non-zero columns of the j-th row of A 2 . We'll refer to |N (j)| as the length of the j-th XOR.

Exponential polytope representation
The simplest encoding is due to Jeroslow [16]. It requires that for all j ∈ J , S ⊆ N (j), and |S| odd, the following should hold Clearly, this requires a number of constraints that is exponential in the length of the XOR.
Another representation exponential in the length of the parity constraint is due to Feldman et al. [7]. For each S in the set E j = {S ⊆ N (j) : |S| even} there is an extra binary variable w j,S ∈ {0, 1}. It requires ∀j ∈ J , S∈Ej w j,S = 1 and ∀j ∈ J , ∀i ∈ N (j), µ i = S∈Ej :i∈S w j,S .

Compact polytope representation
Yannakakis [34] introduced the following compact representation which requires only O(n 3 ) variables and constraints, where n is the number of variables. For each constraint j, define T j = {0, 2, · · · , 2⌊|N (j)|/2⌋} as the set of even numbers between 0 and |N (j)|.
• for all j ∈ J and for all k ∈ T j we have a binary variable α j,k ∈ {0, 1} • for all j ∈ J and for all k ∈ T j and for all i ∈ N (j) we have a binary variable z i,j,k ∈ {0, 1}, 0 ≤ z i,j,k ≤ α j,k 2 To represent the desired parity of the j-th constraint imposed by bj we use a dummy variable d = 1, and include d in N (j) whenever bj = 1.
Then the following constraints are enforced: For any set of parity constraints, these 3 encodings are equivalent, in the sense that the subset of {µ i } satisfying the constraints is the same [7]. Thus, the corresponding MAP inference problems are also equivalent, as the objective function, by expressing each µ i,j in terms of the {µ i } variables, can be re-written as a (possibly non-linear) function of only {µ i }.

SOLVING INTEGER PROGRAMS
Solving ILPs typically relies on solving a sequence of Linear Programming (LP) relaxations obtained by relaxing the integrality constraints. The solution to the relaxation provides an upper bound to the original integer maximization problem. Since LP can be solved in polynomial time, using Theorem 1 and following remarks we have a polynomial time method to obtain approximate upper bounds on the partition function which hold with high probability, although without tightness guarantees. Notice that upper bounds of this form could also be obtained using message passing techniques such as MPLP or TRWBP [9,25,30], which can also provide upper bounds to the values of the MAP inference queries in the inner loop of WISH.
IP solvers such as IBM ILOG CPLEX Optimization Studio [15] solve a sequence of LP relaxations based on branching on the problems's variables, iteratively improving the upper bound and keeping track of the best integer solution found, until lower and upper bounds match. Thus, one advantage of using an IP solver over standard Message Passing techniques is that the upper and lower bounds improve over time, and it is guaranteed to eventually provide an optimal solution for the original integer problem. In Figure 1 we plot the upper bound reported by CPLEX as a function of runtime for a random 10 × 10 Ising model with mixed interactions. It's clear that there is quickly a dramatic improvement over the value of the basic LP relaxation, which is the value reported by CPLEX around time zero, and that the upper bound keeps improving although at a slower rate. We note that other techniques such as by Sontag et al. [25] could also be used to iteratively tighten the LP relaxation, and might lead to better scaling behavior on certain classes of very large problems [35].

INDUCING SPARSITY
As we have shown, solving MAP inference queries subject to parity constraints is hard in general. However, adding parity constraints can sometimes makes the optimization easier. For example, when A is the identity matrix, enforcing Aσ = b mod 2 corresponds to fixing the values of all variables and leads to a trivial optimization problem. Empirically, sparse constraints, such as the ones used in low density parity check (LDPC) codes from Gallager [8], tend to be much easier to solve. Unfortunately, constructions in both Propositions 1 and 2 to create pairwise independent hash functions require parity constraints that are of average length n/2, i.e., the corresponding matrix A is not sparse.
A set of parity constraints specified through matrices A, b defines a set of solutions S = {x ∈ {0, 1} n : Ax = b}, which is the translated nullspace of the matrix A. The nullspace is a vector space, defined with operations over the finite field F(2), i.e. modular arithmetic. Exploiting basic linear algebraic properties, it can be shown that applying elementary row operations to [A|b] does not change the solution set S and thus the optimization problem. On the other hand, the parity polytope we described earlier is not a function of the solution set S but depends explicitly on the form of the matrices A and b. This fact was also noted by Feldman et al. [7], who showed that a new matrix [A ′ |b ′ ] constructed from [A|b] by adding new rows that are linear combinations of the rows of [A|b] can lead to a tighter LP relaxation, although Ax = b and A ′ x = b ′ define the same solution set S (because the constraints added are all implied).
In this paper we propose to exploit these facts and rewrite the constraints in a form that is equivalent, i.e., defines the same set of solutions, but is easier to solve. Specifically, given a a set of parity constraints specified through matrices A, b we look for matrices A ′ , b ′ that define the same set of solutions, namely {x ∈ {0, 1} n : Unfortunately, even finding a sparse linear combination of the rows is computationally intractable, as it can be seen as an instance of MAXIMUM-LIKELIHOOD DECODING, where the code is given in terms of the generators (the rows of A) rather than the check matrix. We therefore propose to use two approaches: • Perform Gauss-Jordan elimination on [A|b] to convert [A|b] to reduced row echelon form; • Try all combinations of up to k rows r 1 , · · · , r k of [A|b], and if their sum r 1 ⊕ · · · ⊕ r k is sparser than any of the r i , substitute r i with r 1 ⊕ · · · ⊕ r k .
Both techniques are based on elementary row operations and therefore are guaranteed to maintain the solution set S and to improve sparsity.
In Figure 2 we show the median upper and lower bounds found by CPLEX for several randomly generated constraints on a random 10 × 10 Ising grid model with mixed interactions. Starting with a matrix A generated using the Toeplitz matrix construction in Proposition 2, we run CPLEX for 10 minutes with and without sparsification, reporting the best upper and lower bounds found. We see that without any preprocessing (NoPre) CPLEX fails at finding any integer solution when there are more than 15 parity constraints. Performing Gauss-Jordan elimination (Diag) significantly improves both the upper bound and the lower bound. The effect is particularly significant for a large number of constraints, when the reduced row echelon form of A is close to the identity matrix. Adding the additional greedy substitution step (DiagGreedy, looking at all combinations of up to k = 4 rows) slightly improves the quality of the upper bound, but the lower bound significantly degrades. Therefore, for the rest of the paper we will use only Gauss-Jordan elimination preprocessing.

LOWER BOUNDS: SHORT XORS
As mentioned in Section 3.2, one practical way to obtain lower bounds from the WISH algorithm is to use suboptimal solutions of the underlying MAP inference problems. Here we explore a different way, namely, using sparse or short parity constraints (XORs), which are often easier for constraint solvers to reason about. This results in a family of hash functions that is uniform but not pairwise independent, leading to a weaker but practically valuable version of Theorem 1.

WISH WITH UNIFORM HASHING
Fix any subset A m×n ⊆ {0, 1} m×n of m × n matrices. We will later create short XORs by choosing A m×n such that every row of every matrix in this set has only k ≪ n/2 non-zero entries. With such a family of hash functions, Theorem 1 as such does not hold, but the following weaker, onedirectional version still does: Theorem 3. For any δ > 0, positive constant α ≤ 0.0042, and families H n,i of uniform (but not necessarily pairwise independent) hash functions, with probability at least (1 − δ), WISH({H n,i }) outputs an estimate no larger than 16Z = 16 σ∈X w(σ).
In other words, even without pairwise independence, the output divided by 16 is a lower bound with high probability. To prove this result, we employ a proof strategy similar to the one used by Ermon et al. [6].
Next we prove a new bound on M i that holds regardless of pairwise independence: Lemma 1. Suppose h i A,b is chosen from a family H n,i of universal (but not necessarily pairwise independent) hash functions. Let M i = Median(w 1 i , · · · , w T i ) be defined as in Algorithm 1 and b i as in Definition 4. Then, for all c ≥ 2, there exists an α * (c) > 0 such that for 0 < α ≤ α * (c), Proof. The statement trivially holds when i − c ≤ 0. Otherwise, let us define the set of the 2 j heaviest configurations as in Definition 4, X j = {σ 1 , σ 2 , · · · , σ 2 j }. Define the following random variable S j (h i A,b ) σ∈Xj 1 {Aσ=b mod 2} which gives the number of elements of X j satisfying the random parity constraints Aσ = b mod 2. The randomness is over the choice of A and b when h i A,b is sampled from H n,i . Since H n,i is a family of uniform hash functions, by definition for any σ the random variable 1 {Aσ=b mod 2} is Bernoulli distributed with probability 1/2 i . Then it follows that The random variable w i is defined as w i = max σ w(σ) subject to Aσ = b mod 2. Then we have: which is the probability that no configuration from X j satisfies i randomly chosen parity constraints. Notice Thus for j = i − c and c ≥ 2, we have:

EVALUATION OF SHORT XORS
As briefly alluded to earlier, we will use short XORs in order to make MAP inference more efficient in practice. Specifically, we will choose A uniformly from A m×n k ⊆ {0, 1} m×n , which is the set of matrices such that every row has only k non-zero entries, where k will typically be much smaller than n/2. In general, smaller values of k lead to faster execution of WISH but at the cost of weaker lower bounds. Figure 3 compares several approaches to solve the MAP inference problems constrained by random parity constraints for a 10 × 10 Ising grid model with attractive and mixed interactions (external field f = 1.0 and weight w = 3.0; see below for a formal description of the probabilistic model used). We compare three message passing approaches, namely Belief Propagation (BP), Max-Product (MP), and MPLP [9], and two combinatorial optimization solvers, namely Toulbar [1] and CPLEX 12.3 [15], both with a 1 minute time limit. We show the median value of the solution found over 50 realizations, for each number of parity constraints added. We run the Message Passing methods until they find a feasible solution satisfying the parity constraints or up to 10000 iterations. If no feasible solution is found, we round the final beliefs to an integer solution and project it on the feasible set by solving the linear equations with Gaussian Elimination, thus changing the value of some of the variables. For this problem, using "long" parity constraints of length 50, Message Passing methods can only find feasible solutions for up to 10 constraints (consistent with CPLEX performance in Figure 2). In contrast, as shown in Figure 3, using short XORs of length 4 (typical values encountered e.g. for low density parity check codes), Message Passing methods can find feasible solutions for up to about 40−50 constraints, at which point there is a significant performance drop caused by the need for a projection step. We see that for the attractive case, Message Passing methods are competitive with combinatorial optimization approaches but only for a moderate number of constraints. In the more challenging mixed interactions case, CPLEX and Toulbar appear to be clearly superior. We think the the unsatisfactory performance of message passing techniques (compared e.g. to when used for LDPC decoding) is caused by the more complicated probabilistic dependencies imposed by the Ising model, which is much more intricate than a typical transmission error model.

EXPERIMENTS
We evaluate the performance of WISH augmented with Toeplitz-matrix based hash functions (from Proposition 2) and CPLEX 12.3 [15] to solve the ILP formulation of the MAP queries. All the optimization instances are solved in parallel on a compute cluster, with a timeout of 10 minutes on Intel Xeon 5670 3GHz machines.We use Gauss-Jordan elimination preprocessing to improve the quality of the LP relaxations. We use the Jaroslow encoding for parity constraints j ∈ J such that |N (j)| ≤ 10, and the Yannakakis encoding otherwise. We evaluate the lower bound and upper bounds for the partition functions of M × M grid Ising models for M ∈ {10, 15}, with random interactions (positive and negative) and external field f ∈ {0.1, 1.0}. Specifically, there are M 2 binary variables, with single node potentials ψ i ( We compare with Loopy BP [23] which estimates Z, Tree Reweighted BP [30] which gives a provable upper bound, and the Mean Field approach [31] which gives a provable lower bound. We use the implementations in the LibDAI library [22] and compare with ground truth obtained using the Junction Tree method [20]. Figure 4 shows the error in the resulting estimates, together with the upper and lower bounds obtained with WISH augmented with Toeplitz-matrix hashing and CPLEX. We immediately see that our lower bounds     are highly accurate (error close to 0), which means that the lower bounds provided by CPLEX for the ILPs must be close to optimality. Similarly good lower bounds can also be obtained using the original WISH algorithm [6], and also using SampleSearch [11]. However, neither SampleSearch nor the original WISH (without LP relaxations) provide upper bound guarantees, only the TRWBP approach does. Specifically, the original WISH algorithm with Toulbar [1] provides an upper bound only upon proving optimality for all optimization instances in the inner loop. In contrast, the ILP formulation provides us with anytime and gradually improving upper bounds based on LP relaxations (cf. Figure 1), often well before it can actually solve the problems to optimality (which might not be possible on larger instances) or, in principle, even before it can find a feasible solution. Figure 4 shows that our upper bounds are significantly tighter than the ones obtained using TRWBP in the hard weights region. Further, our ILP approach is guaranteed to eventually give an accurate answer, within a constant factor, given enough time. In contrast, message passing techniques are usually quite fast (if they converge) but do not provide better results with more runtime.

CONCLUSIONS
We explored several extensions of the recent WISH [6] algorithm for computing discrete integrals. First, we used a better, more deterministic and thus more stable construction for pairwise independent hash functions. Using a connection with max-likelihood decoding of binary codes, we showed that the MAP inference queries generated by WISH are in general not polynomial time solvable or even approximable. On the positive side, this led to the use of an ILP formulation for the problem, inspired by iterative message passing decoding. To increase the practicality of the ILP approach, we sparsified parity constraints while preserving their desirable properties. Further, we extended WISH to directly utilize uniform but not necessarily pairwise independent hash functions, leading to computationally easier optimization problems while still providing probabilistic lower bound guarantees. Finally, we showed that by solving a sequence of LP relaxations we can obtain not only very accurate lower bounds but also upper bounds that are much tighter than the ones provided by TRWBP, which is based on tree decomposition and convexity.