Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm
Gabriel Istrate Cosmin Bonchis Mircea Marin







1,2,*]Gabriel Istrate
1,2]Cosmin Bonchiş
1]Mircea Marin
[1]Department of Computer Science, West University of Timişoara
[2]e-Austria Research Institute
[*]corresponding author email: gabrielistrate@acm.org


















Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm
    [
    Accepted . Received ; in original form 
=====================================================================================




We analyze the expected running time of WalkSAT, a well-known local search procedure for satisfiability solving, on satisfiable instances of the k-XOR SAT problem. We obtain estimates of this expected running time by reducing the problem to a setting amenable to classical techniques from drift analysis. 

A crucial ingredient of this reduction is the definition of (new, explosive) hypergraph versions of interacting particle systems, notably of coalescing and annihilating random walks as well as the voter model. The use of these tools allows to show that the expected running time of WalkSAT depends on structural parameter (we call odd Cheeger drift) of the dual of the formula hypergraph. 



Keywords: XOR-SAT, interacting particle systems, hypergraphs, drift analysis.




§ INTRODUCTION
 

Interacting particle systems are discrete dynamical systems, usually defined on lattices, studied intensely in Mathematical Physics  <cit.>. They can be investigated on finite graphs as well <cit.>, <cit.>, <cit.> as finite Markov chains; some of them correspond via duality to certain types of random walks <cit.>. It is, therefore, not that surprising that the analysis of such particle systems can  sometimes be used to upper bound the mixing time of several Markov chains, e.g. (hyper)graph coloring procedures <cit.>. 

In this paper we consider generalized such models in conjunction with a problem in the rigorous analysis of randomized search algorithms for combinatorial optimization. While progress has been made <cit.>, tools and techniques for the analysis of such methods are still somewhat limited, and our theoretical knowledge still considerably lags that in the experimental investigation of heuristics. 

The problem we deal with is 
the analysis of the local search procedure WalkSAT <cit.>  for a version of the satisfiability problem, the so-called k-XOR-SAT problem, where k≥ 2.  We show that studying hypergraph analogues of coalescing/annihilating random walks and the voter model allows the control of the expected convergence time of WalkSAT on many individual satisfiable instances Φ of  k-XOR-SAT in terms of structural parameters of two associated hypergraphs:

 

  - the formula hypergraph of Φ (for uniquely satisfiable instances)

  - a certain "triadic dual" of this hypergraph (in general) 


The tool we employ is drift analysis <cit.>. 

On a technical level, our models extend the classical versions of annihilating and coalescing random walks,  as well as the voter model to hypergraphs. Besides their intended application to XOR-SAT, such  generalizations have obvious intrinsic interest, and add to the growing recent literature on extending interacting particle systems  to hypergraphs <cit.> and simplicial complexes <cit.>. The analysis we perform also has consequences for several other seemingly unrelated problems, such as   
 social balance <cit.> and  lights-out games <cit.>. 
 
Though inheriting some properties from the graph case, our generalizations  display additional technically interesting features: for instance, in contrast to the graph case (where it is nonincreasing), the number of live particles in annihilating random walks on hypergraphs may go up, and the structure of recurrent states is constrained by systems of linear equations similar to the ones used to analyze lights-out games <cit.>. On the other hand, in  coalescing random walks on hypergraphs there may be more than one copy of an initial "particle" and the process is naturally described using multisets, rather than sets of particles. 


The plan of the paper is as follows: first we define the models we are interested in. In Section <ref> we motivate some of the concepts relevant to our result through the analysis of a particular case. This example can easily be extended to many families of uniquely solvable instances of k-XOR SAT. There are three cases, intuitively corresponding to positive, neutral and negative drift, respectively.  

In section <ref> we reinterpret the dynamics underlying WalkSAT by duality. 
Our main result (Theorem <ref>/Corollary <ref>) extends techniques developed in <cit.> for the analysis of the voter model on finite graphs, bounding the expected convergence time of WalkSAT in terms of two Cheeger-like constants of the dual of the formula hypergraph.  




§ PROBLEM STATEMENT
 
We are concerned with a version of the satisfiability problem called k-XOR satisfiability (k-XORSAT): 

 Given k≥ 2, 
 an instance of k-XORSAT is a linear system of m equations, A·x=b 
 over Z_2, where
 
 
 
 A is an m× n matrix, m,n≥ 1,  

x=(x_1,x_2,…, x_n)^T is an n× 1 vector,  

b=(b_1,b_2,…, b_m)^T is an m× 1 vector, and each equation has exactly k variables. 



Though k-XORSAT can easily be solved in polynomial time by Gaussian elimination, we will not be concerned with 
this algorithm. Instead our aim is to analyze a local search procedure, called WalkSAT <cit.>,  displayed as Algorithm <ref>, and originally investigated on random instances of k-SAT. Though possible in principle in several cases (e.g. <cit.>) and well-understood from the standpoint of Statistical Mechanics <cit.>, 
 such an analysis is still quite complicated in general. 
 
Analyzing WalkSAT on instances of k-XORSAT (rather than k-SAT) is motivated by the empirical observation that "curiously" <cit.> XOR-SAT instances prove even harder for WalkSAT than those arising from k-SAT. On the other hand, one may hope that obtaining a rigorous analysis of WalkSAT may prove more tractable for the better understood problem k-XORSAT. While previous (highly nontrivial) such analyses concentrated on random instances <cit.>,  we show that one can in fact obtain rigorous upper bounds on the expected running time of WalkSAT on individual solvable instances of k-XORSAT, expressed in terms of (measurable) structural parameters of these
individual instances.[we don't mean by this statement that the expected running time may be predictable: these structural parameters may be hard to compute.] We believe that such individual characterizations are important, as they make more transparent the structural properties of the input formula that influence the tractability of algorithms and heuristics. 



First of all, the following easy observation is true:  





Let Φ be a satisfiable instance of k-XOR-SAT. Let X^(1) be an arbitrary assignment. Then a satisfying assignment X^(2) for Φ is reachable from X^(1) by means of moves of WalkSAT.  

 

We prove that a solution of the system is reachable from X^(1) by induction on k, the Hamming distance between X^(1) and the set of solutions of the system A·x⃗ = b⃗ (denote by X a solution satisfying d_H(X^(1),X)=k). 


  * Case k=0. Then X^(1)=X and there is nothing to prove. 

  * Case k=1. Then X^(1) and X differ on a single variable z. Let m be an equation containing z. Then X^(1) does not satisfy m (as X, which only differs on z, does). Choosing equation m and variable z we reach X^(2)=X from X^(1). 

  * Case k≥ 2. If there is an equation w not satisfied by X^(1) (but satisfied by X) then w must contain a variable on which X^(1) and X differ. Let z be such a variable. Then by flipping the value of z in WalkSAT (by chosing clause w) 
one can reach from X^(1) an assignment X^(2) at Hamming distance k-1 from X. Now it is easily seen that system H(X^(2),X) has solutions: any solution of H(X^(1),X) with the value of z flipped.  
By the induction hypothesis one can reach a solution from X^(2), therefore from X^(1). 



Given the previous theorem, the following is a fairly natural research question: 
Given satisfiable formula Φ and initial assignment X, estimate quantity E[T_WalkSAT(Φ,X)], the average number of steps WalkSAT makes on Φ starting from X in order to find a satisfying assignment.


We will answer this question for a large-class of k-XOR-SAT instances by reducing the problem to one amenable to drift analysis <cit.>. There will be two reductions: one (involving the formula hypergraph) works for uniquely satisfiable instances only. The second one reinterprets the dynamics of WalkSAT by duality and uses a "triadic dual" of the formula hypergraph. In this second setting, instances for which drift analysis leads to polynomial time upper bounds will require a mild additional "acyclicity" condition. 



§ OTHER APPLICATIONS


A second application comes from the physics of complex systems and is given by the following dynamics, first investigated by Antal et al. <cit.>: 

 
 Constrained Triadic Dynamics. Start with 
graph G=(V,E) whose edges are labeled 0/1. A
triangle T is G is called balanced if the
sum of its edge labels is 0 (mod 2). At any
step t, we randomly chose an imbalanced triangle T and change the sign of a 
random edge of T (thus
balancing T). The move might, however, unbalance other
triangles.


CTD can be modeled by the WalkSAT algorithm on an instance of 3-XORSAT <cit.>. As further shown in <cit.>, one can sometimes analyze CTD using duality. 

Finally, the particle systems in this paper are related to certain lights-out games <cit.>. More precisely, when viewed by duality (see Section 4), the dynamics considered in this paper corresponds to a hypergraph extension of the lit-only σ^+-game. 

Markov chains based on lights-out games with random moves were recently studied by Hughes <cit.>. As this latter paper deals with a different version of the lights-out game, the two results are not comparable. 



§ PRELIMINARIES
 


We allow hypergraphs with self-loops, i.e. hyperedges e with |e|=1. We will even allow multiple self-loops to the same vertex. A multiset is an unordered container of items whose elements have a (positive) multiplicity. The disjoint union of multisets A and B, denoted A⊔ B, is the multiset that adds up multiplicities of an element in A and B. 

Given hypergraph H=(V,E) and v∈ V we will denote by N(v) its open neighborhood, defined as the set {w≠ v∈ V:(∃ e∈ E), {v,w}⊆ e} and by N[v]={v}∪ N(v) its closed neigborhood. 

Given instance Φ of k-XOR-SAT, the formula graph of Φ, H(Φ) is the hypergraph having variables of Φ as nodes and hyperedges which correspond to equations in Φ. If Φ is satisfiable then H(Φ) will be a simple hypergraph, since for every S⊆ V, Φ can contain at most one equation involving precisely the variables in S. 

We will deal with discrete dynamical systems on hypergraphs. Consider such a d.d.s. 𝒟 on hypergraph H. Given two configurations 
C_1,C_2  of 𝒟, we will use notation C_1⊢ C_2. We also use notation ⊩ to denote the transitive closure of relation ⊢: Specifically, we write C_1⊩ C_2 iff C_2 is reachable from C_1. 

 A satisfiable instance Φ of k-XOR-SAT is connected iff it cannot be partitioned into two non-empty parts, Φ=Φ_1∪Φ_2, with Φ_1,Φ_2 having disjoint sets of variables. 
 

It is reasonable to require that instances of XOR-SAT we want to solve are connected: indeed, if it were not so then one could simply solve XOR-SAT separately on the two instances Φ_1,Φ_2.  

 A satisfiable instance Φ of k-XOR-SAT is cyclic iff every variable appears in an even number of clauses (alternatively, if each equation C of Φ is implied by the conjunction of all other equations of Φ). A formula Φ is acyclic iff no empty subformula of Φ (including Φ istself) is a cycle. 
 

Finally, we will use the following simple result: 
 
Given random variable X with support on Z_+, E[X]=∑_i≥ 0 Pr[X> i].

 




§ A MOTIVATING EXAMPLE


To motivate some of the concepts we will introduce in the sequel,  we first study a particular instance of our problem: 

 
Let n≥ 1, let H be a hypergraph with n vertices and let Z_n=(Z_1,n,Z_2,n,…, Z_n,n)∈{0,1}^n be a boolean vector. We denote by  H(Z_n) the linear system with n boolean variables X_1,X_2,…, X_n and equations
∑_i∈ e X_i=∑_i∈ e Z_i,n, 
where e ranges over all hyperedges of H. 
 

By design H(Z_n) has Z_n among the solutions. 
When H is k-uniform, H(Z_n) is an instance of k-XOR SAT. 
In particular, we refer to K_5(Z_n) as the complete 5-uniform linear system. The reason for this name above is obvious: the formula hypergraph of K_5(Z_n) (having variables as vertices and equations corresponding to hyperedges) is the complete 5-uniform hypergraph. 

The following is an easy observation: 
 
Z_n is the only solution of K_5(Z_n). 

 
 
Subtracting two equations that only differ one one variable (X_i and X_j, respectively) 
we infer X_i-X_j=Z_i,n-Z_j,n for all 1≤ i,j≤ n. Thus the values of all variables are determined by the value of X_1. 

When X_1=Z_1,n we obtain solution Z_n. The alternative X_1=Z_1,n+1 does not lead to a solution, because it corresponds to flipping all bits in Z_1,n, which is not a solution of the system (as all equations have odd width).
 

From Lemma <ref>, to any assignment U_t considered at step t by WalkSAT one can associate a partition (A_t,A_t) of the variables {X_1,X_2,…, X_n} with 
    A_t={X_i: U_t(X_i)≠ Z_i}

denoting the set of "bad variables".  We can analyze the WalkSAT algorithm on K_5(Z_n) by employing the potential function u(t)=|A_t|. Eventually w.h.p. u(t)=0, and the analysis amounts to investigating the expected hitting time of this event. 

WalkSAT evolves by flipping the value of a single variable. Therefore u(t) can either decrease by 1 (if one "bad" variable becomes "good") or increase by one (if one "good" variables flips to "bad"). The following easy observation is crucial: 

 
For t≥ 0, equation e is not satisfied by assignment U_t iff
|Var(e)∩ A_t|
  

This lemma motivates the following rather "exotic" notion of an odd cut in a hypergraph: 


Given hypergraph H and partition V(H)=A∪A, A∩A=∅, define 
 

  - OddCut(A) to be the subhypergraph of H induced by 
edges e such that |e∩ A| is odd. 

  - E^-(A,A) to be the set of pairs (v,e) with v∈ A and e∋ v, e∈ OddCut(A). 

  - E^+(A,A) to be the set of pairs (w,e) with w∈A and e∋ w, e∈ OddCut(A). 
 

 

 
In the definition of OddCut(A),E^-(A,A) we allow (odd-size) hyperedges that may not contain a single vertex from A ! 


  

The connection between these notions and the analysis of WalkSAT is clear: 
 

  - Δ u(t)=+1, precisely when at step t the chosen pair (v,e) belongs to E^-(A_t,A_t). 

  - Similarly, Δ u(t)=-1, precisely when at step t the chosen pair (v,e) belongs to E^+(A_t,A_t).
 

 For a  hypergraph H and set A⊆ V(H) define the 
odd  Cheeger drift D_odd(A) as 

    D_odd(A)=|E^+(A,A)|-|E^-(A,A)|/|E^+(A,A)|+|E^-(A,A)|.

 Note that the odd Cheeger drift D_odd(A) is only well-defined for sets A such that OddCut(A)≠∅.   
 


The characterization of all hypergraphs for which condition  OddCut(A)≠∅ is satisfied for all A is related to parity domination in graphs <cit.>, and is adapted to hypergraphs as follows:  









Given connected hypergraph H=(V,E), set of vertices ∅≠ A⊆ V is even parity dominating in H if for every e∈ E, 
|A∩ e| is even.  H is odd-connected if it has no even dominating set ∅≠ A≠ V.








 

 
 

The introduced terminology allows us to characterize hypergraphs H such that D_odd(A) is well-defined for all ∅≠ A≠ V by the following simple result: 

 OddCut(A)≠∅ holds for all ∅≠ A≠ V(H) iff H is odd-connected.  
 

We also require a specially tailored Cheeger-like quantity, somewhat similar to the definition of coboundary expansion but with an easy combinatorial definition reminiscent of the so-called Cheeger time <cit.>: 

 Given a k-regular hypergraph H define the odd Cheeger time τ_H  as 

    τ_odd(H)=sup_0<|A|≤ |V|nk/|E^-(A,A)|.
 

 


We now return to the definition of odd Cheeger drift in hypergraphs, presenting a couple of examples. The analysis of the hypergraph K_5(Z) in particular, allows us to finally settle the problem investigated in this section: the expected convergence time of WalkSAT on K_5(Z) is exponential. 


 For every k-regular graph G without self-loops, the odd Cheeger drift of an arbitrary set A is zero, as |E^+(A,A)|=|E^-(A,A)| for all A. 



 For every k-regular graph G that may include self-loops, the odd Cheeger drift of an arbitrary set A is ≥ 0. More precisely, if L(A) is the multiset of self-loops of vertices in A, 

    D_odd(A)=|L(A)|/2· |OddCut(A)|-|L(A)|


Indeed, all edges e∈ OddCut(A) that are not self-loops contribute both to E^+(A,A) and E^-(A,A). On the other hand self-loops only contribute to E^-(A,A). 



Let H=K_n,5 be the complete 5-uniform hypergraph with n vertices. 
Then the odd Cheeger drift of arbitrary low-density subsets of H will be negative (for large values of n). Indeed, if |A|=δ n, the number of hyperedges e containing 
 

  - five vertices in A is δ n5∼δ^5/5!n^5. Each vertex v∈ e will count for E^-(A,A) in pair (v,e)

  - three vertices in A is 
δ n3(1-δ) n2∼ n^5 δ^3(1-δ)^2/12. These three vertices will count for E^-(A,A), the other two for E^+(A,A). 

  - 
exactly one vertex in A is δ n(1-δ) n4∼ n^5 δ(1-δ)^4/24. This vertex will count for E^-(A,A), all the rest for E^+(A,A).
 

Thus, as n→∞ 

    |E^-(A,A)|= n^5[δ^5/24+3δ^3· (1-δ)^2/12+δ (1-δ)^4/24](1+o(1))


On the other hand 

    |E^+(A,A)|= n^5[2δ^3 (1-δ)^2/12+4δ(1-δ)^4/24](1+o(1))


Trebuie schimbata formula E+ si se schimba putin plotul driftul dar nu semnificativ. 


    E^-    =     5δ^5/5!+3δ^3(1-δ)^2/3!2!+δ(1-δ)^4/4!
        =    δ^5/24+δ^3(1-δ)^2/4+δ(1-δ)^4/24
        =    δ^5+6δ^3(1-δ)^2+δ(1-δ)^4/24
    
    
    
    E^+    =     2δ^3(1-δ)^2/3!2!+4δ(1-δ)^4/4!
        =    δ^3(1-δ)^2/6+δ(1-δ)^4/6
        =    4δ^3(1-δ)^2+4δ(1-δ)^4/24




    E^--E^+/E^-+E^+    =    [δ^5+6δ^3(1-δ)^2+δ(1-δ)^4]-[4δ^3(1-δ)^2+4δ(1-δ)^4]/[δ^5+6δ^3(1-δ)^2+δ(1-δ)^4]+[4(δ^3(1-δ)^2+δ(1-δ)^4)]
        =    δ^5+2δ^3(1-δ)^2-3δ(1-δ)^4/δ^5+10δ^3(1-δ)^2+5δ(1-δ)^4
        =    δ^4+2δ^2(1-δ)^2-3(1-δ)^4/δ^4+10δ^2(1-δ)^2+5(1-δ)^4








"Asymptotic drift" quantity 

    D_odd(δ)     =
    lim_n→∞, |A|=δ n|E^-(A,A)|-|E^+(A,A)|/|E^-(A,A)|+|E^+(A,A)|
        = δ^4+2δ^2(1-δ)^2-3(1-δ)^4/δ^4+10δ^2(1-δ)^2+5(1-δ)^4
 
 is plotted 
against density parameter δ in Figure <ref>.  Note that the asymptotic drift is negative for δ < 1/2. This allows us to employ drift analysis to prove an exponential lower bound on the expected convergence time of WalkSAT:

 



 




There exist constants ϵ > 0, 0<d<1 and c>1 such that for all large enough n≥ 1 and any initial assignment X_1,n with d_H(X_1,n,Z_n)>n(1/2-ϵ), the expected convergence time of WalkSAT on system K_5(Z_n) starting from initial assignment X_1,n is at least 
 c^n (1-d). 

 
 
A consequence of drift analysis. Formally, take n large enough such that -1< D_odd(A)< -0.1 for all A with 0.1n<|A|< 0.2n. Then choose e.g. ϵ = 0.1 and apply the  Simplified Drift Theorem <cit.>, inferring that there exist constants c>1>d>0 such that Pr[T< c^n]< d^n. Therefore the expected time to hit zero is at least c^n(1-d^n). 


 

One can easily extend this example, as follows: 



Given family Φ=(Φ_n) of connected, uniquely satisfiable instances of k-XOR-SAT, the following statements hold:  

 

  (i). Suppose there exists constant δ >0  such that for all nonempty sets A⊂ V,  D_odd(A)≥δ. Then 

    max_X_n∈{0,1}^n E[T_WalkSAT(Φ_n,X_n)]≤ T(n),


where T(n) is a function such that 

    T(n)=O(n).


  (ii). Suppose case 1 does not apply but D_odd(A)≥ 0 for every nonempty set A. Then inequality (<ref>) holds with 

    T(n)=O(n^2τ_odd(H(Φ_n))).

 
On the other hand, given family Φ=(Φ_n) of connected instances of k-XOR-SAT, the following statement holds:  
  

  (iii). Suppose there exist 0<η_1<η_2< 1 and δ >0 such that for all  sets 
A⊂ V with η_1n<|A|<η_2n we have D_odd(A)<-δ. Then for any sequence of assignments X_n with |X_n|≥η_2n,  

    E[T_WalkSAT(Φ_n,X_n)]≥ T_H(n),


where T_H(n) is a function such that

    T_H(n)=Ω(e^Ω(n)).

 

 


Case (i)., a positive drift case, is easily analyzed as follows: First, rewrite drift condition as 

    E[Δ u(t)]=Prob[Δ u(t)= 1]- Prob[Δ u(t)= -1]≤ -δ/k (*)
  Because probabilities above belong to interval (0,1), -1≤ E[Δ u(t)]≤ -δ. Also 

    Prob[Δ u(t)= 1]= 1/2[(Prob[Δ u(t)= 1]+ Prob[Δ u(t)= -1])+ 
     (Prob[Δ u(t)= 1] - Prob[Δ u(t)= -1])]≤1/2-δ/2

and 

    Prob[Δ u(t)= -1]≥  Prob[Δ u(t)= 1]+ δ/k≥δ.

  In fact, as long as u(t)>0, Δ u(t) can be stochastically upper bounded by a random variable X_t taking only values -1,0,1 which has  the following properties:
  
 
  (a). Pr[X_t=0]=Pr[Δ u(t)=0]. 
 
  (b). E[X_t]=Pr[X_t=1]-Pr[X_t=-1]=-δ
  
 To accomplish this, we simply "move mass" in Δ u(t) from value -1 to +1. There is "enough mass" at -1 because of (*). 

Since hyperedge choices are independent, random variables Δ u_t are also independent and we can take their dominating random variables X_t  
to be independent too. 

Given arbitrary independent random variables Z_t with values in -1,0,1 and E[Z_t]=-δ define 
chain (Y_t) by Y_0=Z_0, Y_t=Y_t-1+ Z_t. By standard application of elementary hitting time techniques (such as the forward equation and generating functions) to chain Y_t 
we infer E_Y_0 [T_{Y_t=0}]= Z_0/δ. Applying this to chain Z_t=Δ u(t) (or, rather to Z_t=Y_t) we infer 

    E[T_{u(t)=0}] ≤ n/δ:=T(n).


Case (ii): The argument is similar: we couple the process with a random walk Y_t on the integers with a reflecting (upper bound) barrier  at n. We do so by requiring that for every 0≤ k< n, Pr[Δ u(t)=0 | u(t)=k]=Pr[Δ Y_t=0 | Y_t=k], 
and redistributing the remaining probability equally between Pr[Δ Y_t=-1 | Y_t=k] and Pr[Δ Y_t=1 | Y_t=k]. From the hypothesis, u(t) can be stochastically dominated by Y_t, so upper bounds for the maximum hitting time of Y_t upper bound the maximum hitting time of u(t) as well. 

By the definition of Y_t 





    Pr[Δ Y_t=-1 | Y_t=k]=Pr[Δ Y_t=1 | Y_t=k]= 
       1/2(Pr[Δ u(t)=-1 | u(t)=k]+Pr[Δ u(t)=-1 | u(t)=k])≥
       1/2(Pr[Δ u(t)=-1 | u(t)=k] 
    ≥1/2·1/τ_odd(H(Φ_n)).

 Now we apply to chain Y_t Lemma 10 from <cit.>), Chapter 14, comparing Y_t with the simple unbiased lazy random walk on the integers, whose maximum hitting time is Θ(n^2) The conclusion is that T(n) can be taken to be O(n^2·τ_odd(H(Φ_n))).  

Case (iii). is proved using an argument similar to that of  Theorem <ref>. 
 












§ BEYOND UNIQUE SATISFIABILITY.


The previous section showed the relevance of concepts such as odd cuts and odd Cheeger drift in the analysis of  algorithm WalkSAT. However, the unique satisfiability restriction on formulas is a serious restriction, that hampers the practical applicability of the result: it is not even clear that uniquely satisfiable formulas falling into Cases (i) and (ii). of the theorem exist ! A difficulty in extending the analysis beyond the uniquely satisfiable case is the lack of a good analog of the progress measure u(t): when the system has multiple solutions the set of variables can no longer be partitioned into good and bad ones. In such cases the formula may still have a backbone or spine <cit.>, but typically <cit.> formulas  have "minibackbones" corresponding to local clusters of solutions, whose values differ between the exponentially many different clusters. Some variables may be outside the 2-core of the formula hypergraph, playing no role in its satisfiability, but be dependent on the variables in the 2-core (and possibly important in the dynamics of WalkSAT).

In this section we show that a different route works sometimes: rather than concentrating on variable-based measures of progress, we will instead concentrate on the dynamics of  clause-based measures. The analysis will require us to consider structural properties of the dual of the formula hypergraph: 


 Given instance Φ of k-XORSAT, the triadic dual  D(Φ) of Φ is an undirected
hypergraph with self-loops
D(Φ)=(V,E) defined as
follows: V is the set of equations of
Φ. Hyperedges in D(Φ) correspond to variables in Φ
and connect all equations 
containing a given variable. In particular
we add a self-loop to an equation (vertex) v if it contains a variable appearing only in 
v. We may even add multiple self-loops to the same vertex. In other words D(Φ) is simply the dual of the formula hypergraph of Φ. 



Note that if Φ is an instance of k-XORSAT then D(Φ) is a k-regular hypergraph (i.e. every vertex has degree exactly k). Examples of duality are displayed in Fig. <ref> and <ref>. In both cases the border nodes, edges in the primal hypergraph correspond to variables of the formula, and triangles to equations; vertices of the dual correspond to equations as well. Self-loops in the dual, correspond to variables in the primal formula appearing exactly in one equation. 

 

Consider Let 1≤ r≤ n and let u:nr→{0,1}, where by nr we have denoted the family of subsets of {1,2,…, n} having exactly r elements. Define system H(n,r,u) by equations: 

    ∑_A∈nr, A∋ i X_A=∑_A∈nr, A∋ i u(A).

H(n,r,u) is a satisfiable instance of nr-XOR-SAT.  Its triadic dual, 
D(H(n,r,u)), is isomorphic to the complete r-ary hypergraph K(n,r). 
 










Odd-connected hypergraphs capture an important class of formulas: 

 
Instances Φ of k-XOR-SAT is acyclic iff the triadic dual of its formula graph is odd-connected. 
 
 
Vertices of D(Φ) correspond to clauses of Φ. An even cut of D(Φ) corresponds to a subformula Φ_1 of Φ such that every variable in Φ appears in an even number of clauses of Φ_1, i.e. to a cycle. 
 


 
For any instance Φ of k-XORSAT let Z be an assignment to the variables of Φ. Let C_Z be the configuration on D_Φ (called the configuration dual to  Z) defined as follows: a vertex v has label 1 in C_Z if and only if the corresponding equation is satisfied by Z.  
 
The restatement by duality of Theorem <ref> is the following: 

 
Let Φ be a satisfiable instance of k-XOR-SAT. Let w_1 be the configuration in the hypergraph D(Φ) corresponding to X^(1) and let w_2 be the "all-zeros" configuration. Then w_2 is reachable from w_1. 

 


The starting point of our analysis is the translation by duality of WalkSAT: 

 
For any instance Φ of k-XORSAT let X_0 be an initial assignment to the variables of Φ. Let C(X_0) be the configuration dual to X_0. Suppose the algorithm WalkSAT on Φ with initial assignment X_0 changes variable x in (unsatisfied) clause C, resulting in assignment X_1. Then the configuration C(X_1) dual to X_1 is obtained by flipping the values of those nodes in hyperedge x of D_Φ (which contains node C whose initial value was 1).  
 
 
By changing the value of variable x any equation that contains x and was satisfied by X_0 becomes unsatisfied by X_1 and viceversa. On the dual this reads as follows: every vertex of the hyperedge that corresponds to variable v changes value. 
 

Translation by duality motivates the following definition:  


Let H=(V,E) be a connected hypergraph. Define an annihilating random walk on H (Figure <ref>) by the following:
 

  (a).
 Initial state: Initially: A_i∈{0,1}. We identify this configuration with  ℬ={i∈ V:A_i=1}, and call such a vertex i live. 
 
  (b).
 Moves: Choose pair i,e consisting of a random live node i and a random hyperedge e=(i,j_1,…, j_k) containing i. Simultaneously set A_v=A_v⊕ A_i for all v∈ e (including v=i, which will result in A_i=0).  
 
  (c). Annihilation: The event we want to time is annihilation, defined by condition A_v=0 for all  v. 
 
  (c). Stabilizing configurations: To be able to talk about the expected time to annihilation we will limit ourselves to stabilizing configurations, i.e. configurations C of the annihilating random walk such that the annihilating configuration 0 is reachable from C and all its descendants. We will denote the set of stabilizing configurations of G by 𝒮(G). As implicitly shown in Theorem <ref>, configurations ℬ obtained by duality from assignments to satisfiable instances of XOR-SAT are indeed stabilizing. 
   
  
  





Our main result bounds the convergence time of the annihilating random walk on a connected hypergraph. By duality, it yields estimates of the expected convergence time of algorithm 
WalkSAT on a satisfiable k-XORSAT instance  Φ. Such bounds are similar to the ones in Theorem <ref>, except that the relevant quantity turns out to be the odd Cheeger drift of the triadic dual hypergraph D(Φ):


 Given family H=(H_n) of odd-connected hypergraphs, the following statements hold:  


 

  (i). Suppose there exists constant δ >0  such that for all nonempty sets A,  D_odd(A)≥δ. Then 

    max_ℬ∈𝒮(H_n) E[c_ann(H_n, ℬ)]≤ T_H(n),


where T_H(n) is a function such that 

    T_H(n)=O(n).


  (ii). Suppose case 1 does not apply but D_odd(A)≥ 0 for every nonempty set A. Then inequality (<ref>) holds with 

    T_H(n)=O(n^2τ_odd(H_n)).

 
On the other hand, given family H=(H_n) of connected hypergraphs, the following statements hold: 
 

  (iii). Suppose there exist 0<η_1<η_2< 1 and δ >0 such that for all  sets 
A⊂ V with η_1n<|A|<η_2n we have D_odd(A)<-δ. Then for any sequence of stabilizing sets ℬ_n with |ℬ_n|≥η_2n,  

    E[c_ann(H, ℬ_n)]≥ T_H(n),


where T_H(n) is a function such that

    T_H(n)=Ω(e^Ω(n)).


 

 



Given family Φ=(Φ_n) of  acyclic instances of k-XOR-SAT, the following statements hold:  

 

  (i). Suppose there exists constant δ >0  such that for all nonempty sets A,  D_odd(A)≥δ. Then 

    max_X_n∈{0,1}^n E[T_WalkSAT(Φ_n,X_n)]≤ T(n),


where T(n) is a function such that 

    T(n)=O(n).


  (ii). Suppose case 1 does not apply but D_odd(A)≥ 0 for every nonempty set A. Then inequality (<ref>) holds with 

    T(n)=O(n^2τ_odd(D(Φ_n))).

 
On the other hand, given family Φ=(Φ_n) of connected instances of k-XOR-SAT, the following statement holds:  
  

  (iii). Suppose there exist 0<η_1<η_2< 1 and δ >0 such that for all  sets 
A⊂ V with η_1n<|A|<η_2n we have D_odd(A)<-δ. Then for any sequence of assignments X_n with |X_n|≥η_2n,  

    E[T_WalkSAT(Φ_n,X_n)]≥ T_H(n),


where T_H(n) is a function such that

    T_H(n)=Ω(e^Ω(n)).

 

 

A few comments on the bounds on T_H(n) from the above result are in order:  


  - Proving such bounds will require hypergraph analogues of annihilating and coalescing random walks, as well as of the voter model. Unlike their graph counterparts, the ordinary  variants of random walks on hypergraphs <cit.> or the recently defined s-walks <cit.>, these models will be explosive: the number of "particles" may in generally increase at a given step and be unbounded (for  CRW and the voter model). Such properties make these models qualitatively different from their graph versions.   


  - Our result can be restated as the claim that the odd Cheeger drift dictates the nature of the convergence time of 
the multiset voter model (and, with it, of the application to algorithm WalkSAT). Of course, drift-based methods are well established in the analysis of local search heuristics <cit.>. Our contribution is, therefore, the identification of the odd Cheeger drift as the relevant quantity driving the dynamics of 
WalkSAT.

  - Conditions in Cases (i), (ii) are, of course, not exhaustive. They are chosen by analogy with the (first two) possible situations in drift analysis (and, more generally, in that of mixing in Markov chains) with tractable/intractable behavior arising from the connectedness of the configuration space (expansion and the existence of a bottleneck cut, respectively) 



  - The result arises from considering the evolution in time of N_t, the number of vertices having an odd number of opinions in the multiset voter model (or, equivalently of the coupled two-state voter model). In one update step N_t can only go up/down by 1 or stay the same. On the other hand, for odd-connected hypergraphs H, state 0 is the only absorbing state of the two-state voter model: for every configuration C different from 0 at least one edge e has an odd number of ones in C. Let v be a vertex in e labeled 1 in C. Scheduling pair (v,e) decreases the number of ones. 


  - In case (i). of the Theorem the walk has a positive bias towards zero. The convergence time is therefore linear. In case (ii). the random walk is at worst unbiased. It will hit zero only as a result of diffusive behavior. The convergence time would be quadratic if the probability of moving to the left/right would be (lower bounded by) a constant. It is not in general, thus we need to slightly alter the result to take into account this phenomenon. The Cheeger constant appears in the final upper bound. 

 


 Case (i). of Corollary <ref> is illustrated by instances whose formula hypergraph are the triadic cycle (Figure <ref>). The triadic dual T_3(G) of this graph is depicted in Figure <ref> as well. By the computation in Example 2 in Section 3, for every A⊆ V(T_3(G)) 

    D_odd(A)=|A|/2|Oddcut(A)|-|A|≥1/3.

Indeed, the last inequality is equivalent to 4 |A|≥ 2 |OddCut(A)| which is evident, since each node in A has degee 3 and a self-loop, hence at most two adjacent edges in OddCut(A). 

We infer that the convergence time of WalkSAT on the corresponding XOR-SAT instance is linear. 
 


 
An example of a family of formulas falling in the case (ii). of the Corollary is a slight modification of the example in Figure <ref>, the hexagonal finite section of the triangular lattice: take two congruent copies of a hexagonal section of the triangular lattice. Place each of them on a hemisphere, gluing the boundary edges to the equator. Glue the two hemispheres into a sphere, obtaining a graph G_n. One can easily create a family of instances whose formula graph is isomorphic to G_n: for each edge of G_n consider value u(e)∈{0,1}. Define satisfiable instance H(n,H_6,u) of 3-XOR-SAT by adding for each triangle of G_n composed of, say, edges e_1,e_2,e_3, equation 

    X_e_1+X_e_2+X_e_3= u_e_1+u_e_2+u_e_3.


The triadic dual of this formula may be represented on the sphere as well, and is a graph without loops (hence falling, by Example <ref>, into Case 2 of Corollary <ref>) consisting of regular hexagons, with the exception of the patches across the equator, where hexagons and rectangles alternate. 

We don't know how to compute the Cheeger time of this class of examples, though. 
 




Systems H(n,k,u) from Example <ref> fall into Case (iii). of Corollary <ref>. The proof of this statement is similar to that of Example <ref>. 
 




 §.§ Annihilating random walks: reachability, recurrence and stabilization
 

If the hypergraph H is actually a graph without loops, the long-term structure of configurations of the annihilating random walk is simple: either a single live particle survives (if |V(H)| is odd) or none do. In the general case the nature of recurrent states may be more complicated: the number of live particles does not always (weakly) decrease, as it does the case in the graph setting. There may be, therefore, recurrent states different from 0 and those states with a single live node. A necessary condition for reachability was given in <cit.>:  



For every pair of boolean configurations
w_1,w_2:V(H)→ Z_2 on hypergraph H we
define a system of boolean linear equations H(w_1,w_2) as
follows: Define, for each hyperedge e a variable z_e with
values in Z_2. For any vertex v∈ V(H) we define the
equation

∑_v∈ ez_e=w_2(v)-w_1(v).

In the previous equation the difference on the right-hand side is
taken in Z_2; also, we allow empty sums on the left side.
System H(w_1,w_2) simply consists of all equations, for all v∈ V(H).



If x is a state on H and l is a hyperedge of H, define

 x^(l)(v)=
               1+x(v),v∈ l, 
           x(v),
             





 
 If w_2 is reachable from w_1 then system 
 H(w_1,w_2) has a solution in Z_2.





Let P be a path from w_1 to w_2 and let z_e be the number of times edge e is used on path P (mod 2). Then (z_e)_e∈ E is a solution of system H(w_1,w_2). Indeed, element w(v) (viewed modulo 2) flips its value any time an edge containing v is scheduled.




In <cit.> a partial converse of Lemma <ref> was claimed. As we show in the Appendix (Theorem <ref>) such a result is, however, not true, not even in restricted settings. This motivates the following 

 What is the complexity of deciding the following problem:  Given connected hypergraph H and two configurations w_1,w_2 of an annihilating random walk on H, is w_2 is reachable (recurrent) from w_1 ?
 

Note, however, that in the case we are interested in, the one corresponding to the setting of a satisfiable XOR-formula,  we have w_2=0 and 
we do have a converse, which yields an easy characterization of stabilizing configurations for the annihilating random walk: 

 
Configuration w_1 is a stabilizing configuration for the annihilating random walk on H if and only if the system H(w_1,0) has a solution in Z_2. 
 
 

Necessity follows by Lemma <ref>. 

Suppose now that w_1 is a configuration on hypergraph H such that system H(w_1,0) has a solution u∈Z_2. Thus 
w_1[v]=∑_e∋ v u(e). 

Consider the system S naturally corresponding to H. That is, variables x_e of S correspond to hyperedges e of H. Equations of S are defined to be 

    ∑_e ∋ v x_e= w_1[v] (=∑_e∋ v u(e)), v∈ V(H).

S is satisfiable (since u is a solution), hence starting with any initial assignment X_1 (in particular X_1≡ u) we will reach a solution X_2. But the configuration corresponding to X_1 is indeed w_1, and the configuration corresponding to X_2 is 0. 

 






§ THEOREM <REF>: PLAN OF THE PROOF
 

In order to prove Theorem <ref>, it will prove more convenient to analyze annihilating random walks on k-uniform hypergraphs with one additional twist: we will study the lazy version of a.r.w., the one in which the choice of node i is not restricted to live nodes only.  More precisely, moves are specified as follows: 
 

  - Choose random node i and random edge (i,j_1,…, j_k) containing i. 
  - Simultaneously set A_v=A_v⊕ A_i for all v∈ e (including v=i, which will result in A_i=0). 
 


Making the a.r.w. lazy increases, of course, the annihilation time, thus providing an upper bound on the convergence time of the WalkSAT algorithm in the dual model. 

The plan of the proof can be described as follows: 
 

  - We will control annihilation using another IPS, an extension of coalescing random walks to hypergraphs. 

  - We introduce an extension of the voter model to hypergraphs called the multiset voter model and extend the classical duality <cit.> between coalescing random walks and voter model to their new (explosive) versions. 

  - We introduce a two-party version of the multiset voter model and analyze it in terms of a "Cheeger-time." 
 





§ EXPLOSIVE RANDOM WALKS AND INTERACTIVE PARTICLE SYSTEMS ON HYPERGRAPHS.
 



Next we define an analogue of coalescing random walks for hypergraphs (Figure <ref>): 

 
Let H=(V,E) be a connected hypergraph. Each vertex holds a multiset of labels A_i. 
Define a coalescing random walk on H by the following: 


  (a). Initial state:
 A_i⊆{i}. Note that ℬ:= A_1∪ A_2∪…∪ A_n⊆ [n]. We will call a vertex i with |A_i|= odd live. 

  (b). Moves: Given node i and hyperedge e=(i,j_1,j_2,…, j_k) 
updating pair (i,e) 
 proceeds by making A_j_r:=A_j_r⊎ A_i, for r=1,…, k and A_i=∅. Here ⊎ refers to the multiset sum, i.e. union with multiplicities. Note that the move never destroys any label (always A_1∪ A_2∪…∪ A_n=[n]) but may make some indices i satisfy  |A_i|= even. 

  (c). Parity (coalescence) from 𝒜 on ℬ: Given sets of vertices 𝒜, ℬ⊆ V(G), c_coal(H, ℬ) is the minimum t≥ 0 such that, if starting with A_v={v} when v∈𝒜, A_v=∅ otherwise, at time t |A_j| is even for every  j∈ℬ. 


 
 




Finally, we present the "dual" to CRW, a multiset voter model (Figure <ref>):  

 
Let H=(V,E) be a connected hypergraph. Define a multiset voter model on H by the following: 
 

  (a).
Initial state: A_i={i}. Note that A_1∪ A_2∪…∪ A_n=[n]. 

  (b).
Moves: Given node i and hyperedge e=(i,j_1,j_2,…, j_k), 
updating pair (i,e) results in setting A_i=⊎_r=1^k A_j_r. Note that the operation may decrease the number of different "opinions" present in the system, if such opinions were only held by node i. 

  (c).
Parity of opinions on ℬ (from 𝒜): Given 𝒜,ℬ⊆ V(H), parity time c_VM(H,ℬ,𝒜) is the minimum time t such that every initial opinion from 𝒜 is present an even number of times (perhaps zero) among nodes in ℬ. We will omit the second argument when 𝒜=V.
 
 







 §.§ Coupling annihilating and coalescing random walks
 


A particular setting we would like to investigate is given by our motivating examples: the XOR-SAT problem if the system has a solution and the CTD for social balance. With these cases in mind we define the annihilation time for ARW on hypergraphs: 


Given set of vertices ℬ⊆ V(G), c_ann(G,ℬ) is the minimum t≥ 0 such that in the a.r.w on G started with A_i=1 if i∈ℬ, A_i=0 otherwise, at time t we have A_i= 0 for all  i.  
 

We now extend a coupling argument valid in the case of graphs: 



 Suppose G is a connected hypergraph and ℬ⊆ V(G) is stabilizing. Then 
 

  - in the coalescing random walk on G starting from ℬ one can reach coalescence. 

  - one can couple the coalescing and annihilating random walks on G such that
 
    c_ann(G, ℬ)= c_coal(G,ℬ).


  - a similar result holds for the lazy versions of c.r.w./a.r.w as well. 
 
 
 
  

We will define the following stochastic process P: 

 

  * Initial state: A_i={(i,∞)} for i∈ℬ, A_i=∅ otherwise. Note that A_1∪ A_2∪…∪ A_n=ℬ×{∞} and that each A_i contains at most one index b_i with (b_i,∞)∈ A_i. We will call such a multiset live and b_i the witness for A_i. Also denote B_i=A_i∖{(i,∞)} if i is live, B_i=A_i otherwise. 

  * Move: At time t: Choose random vertex i (not necessarily live). Choose random edge (i,j_1,…, j_k). For r=1,…, k 
 

  * If both A_i,A_j_r are live then make A_j_r= (B_i⊔ B_j_r)⊔{(b_i,t),(b_j_r,t)}.

  * If, on the other hand,  at most one of A_i,A_j_r is live then make A_j:=A_i⊔ A_j_r. 
 
Finally make A_i=∅. Note that if we "move" a dead set A_i to a live multiset A_j then A_j will still be live. 

  * Stopping: Stopping time c_P(G) is the minimum t≥ 0 such that at most one i is live (one if n is odd, none if n is even)
 

 The following are true: 
 

  * P observed on [n]×{∞}  and moves of live multisets only (Figure <ref>) is the annihilating random walk on G starting from configuration ℬ.  If n is even then at time c_P(G) all particles have annihilated. Consequently c_ann(G, ℬ)≤ c_P(G, ℬ). 

  * P where we disregard second components in all pairs Figure <ref>) is identical to the coalescing random walk on G and
c_P(G, ℬ)=c_coal(G,ℬ). 
 
 

A "proof by picture" is given in Figure <ref>. There are two cases: j is live or not. In both cases the observed process is identical to the annihilating random walk. Note that if n is even then when coalescence occurs in the c.r.w. all particles have died in the a.r.w.











 §.§ Duality of coalescing random walks on hypergraphs and the multiset voter model


The reason a result such as Theorem <ref> is interesting is that on graphs (see <cit.>) c_coal(G) is identical (via duality) to coalescence time of voter model c_VM(G), which can in turn be upper bounded in terms of a so-called Cheeger time of graph G, essentially the inverse of the more well-known Cheeger constant of G. 

Similar results holds on hypergraphs, although we will need to give them in a slightly more general form: 

 Let H be a connected hypergraph and ℬ be a stabilizing configuration on H. Then the following are true: 
 

  - one can reach parity on ℬ in the multiset voter model.

  - the coalescence time c_coal^lazy(H,ℬ) of the lazy c.r.w. and the parity time of the associated multiset voter model c_VM(H,ℬ) are identically distributed.
  

 

The proof is an adaptation of the classical duality argument <cit.>: we will define a process on oriented hyperedges in H (that is edges with a distinguished vertex) that will be interpreted in two different ways: as parity in the multiset voter model and coalescence in the coalescing random walk. 

The process is described in Figure <ref>. There is a certain difficulty in correctly drawing pointed events in hypergraphs. In the figure we represent hyperedges vertically at the moment the given hyperedge event occurs (times t_1 and t_2 in the coalescing random walk), but this may be more difficult to draw if the vertices of a hyperedge are not contiguous. Horizontal lines (e.g. for ball 3 between moments t_1 and t_2) refer to histories not interrupted by any hyperedge event between the corresponding times. A horizontal line may be interrupted by a hyperedge event. In the interest of readability we chose to drop some horizontal lines from the picture (e.g. at node 3 between time 0 and t_1).

A left-right path P between node i and node j is a sequence of hyperedge events and horizontal lines such that: 
 

  * P starts with a horizontal line of node i and ends with a horizontal line of node j. 

  * Every horizontal line of a node is followed by a hyperedge event with the corresponding node being pointed. 

  * Every hyperedge event is followed by an unique horizontal line corresponding to a non-pointed node.
 

For instance, in the picture from Figure <ref> we have represented three left-right paths, between node 2 and each of nodes 1,4,5. 


In the c.r.w. the activation of hyperedge e=[j→ i_1,i_2,… i_r] pointed at j is interpreted as vertex j being chosen (together with edge e), thus sending a copy of its cluster of balls to all other neighbors. In the multiset voter model the activation of the same pointed hyperedge is interpreted as j adopting the multiset union of opinions of i_1,i_2,…, i_r. 











Just as in the ordinary c.r.w./voter model, the existence of a left-right path between nodes i and j (e.g. 
(2,1),(2,4),(2,5)) is interpreted as the event: 
 

  * "at t_0 node j holds a ball with label i." (in the c.r.w.). 

  * "at t_0 node i holds opinion j with multiplicity at least one." (in the multiset voter model) 
 

Moreover, one path may contribute (when it does) with exactly one ball/opinion of a given type. Consider now the event: "at t_0 every node in ℬ on the right-hand side is connected to nodes on the left-hand side by an even number of paths". 

 

  * In the coalescing random walk this is equivalent to "at t_0 we have parity from ℬ"

  * In the multiset voter model this is equivalent to "at t_0 we have parity of opinions on ℬ"
 



Suppose (for a different example) that in the lazy coalescing random walk in Figure <ref> we start with balls at node set ℬ={2,4}, i.e. the initial state of the system at time 0 is S_0=[∅, {2},∅, {4},∅ ]. Then at time t_0 the system is in the state S_1=[{2}, ∅, ∅, {2,4},{2} ]. Nodes 1,5 have an odd number of balls, while 2,3,4 have an even number. If we were to run the lazy annihilating random walk, nodes 1,5 would be those that still have a particle, while 2,3,4 don't. 

In the voter model (displayed with time going backwards) we start with state V_0=[{1}, {2},{3},{4},{5} ] and end up with state V_1=[{1}, {1,4,5},{4,5},{4},{5} ]. Values 1,5 are those that have not yet reached parity on set ℬ={2,4}, while 2,3,4 have. 
 



 §.§ The multiset voter model and its two-party counterpart


Upper bounding the coalescence time of the voter model on graphs can be achieved <cit.> by coupling it with a "two-party" counterpart and analyzing this latter model instead. In the sequel we accomplish a similar task on general hypergraphs:  

Let H=(V,E) be a connected hypergraph. Define the two-party voter model on H by the following: 


  (a). 
Initial state: A_i∈{0,1} for all i∈ V. We denote 𝒜={i∈ V: A_i=1}. 

  (b). 
Moves: Given node i and hyperedge e=(i,j_1,j_2,…, j_k), 
updating pair (i,e) results in setting A_i=⊕_r=1^k A_j_r, keeping all values A_j_r unchanged. 

  (c). 
Parity of opinions on ℬ: Given 𝒜,ℬ⊆ V(H), the parity time c_2-VM(H;𝒜,ℬ) is the minimum time t such that, starting from configuration 𝒜, at time t and subsequently ⊕_i∈ℬ A_i=0.
 

Note that, unlike the multiset voter model, in the two-party voter model we allow initial states 𝒜 where at time t=0 "some nodes do not hold any opinion". 


 Let H be a connected hypergraph and ℬ⊆ V(H) be a stabilizing set. Then 
 

  - for every set 𝒜⊆ V(H), in the two-party voter model started from configuration 𝒜  one can reach parity of opinions on ℬ.

  - 
for every 𝒜⊆ V(H) 
one can couple the multiset voter model and the two-state voter model with initial state 𝒜 such that whenever we have parity on ℬ in the multiset voter model we have parity of opinions on ℬ from 𝒜 in the two-party voter model.

 
 
 

The first part follows by duality of the multiset voter model and the lazy c.r.w.: by Theorem <ref>, since ℬ is stabilizing, one can reach parity 
from ℬ in the c.r.w. Therefore in the multiset voter model one can reach parity on ℬ from V, hence from 𝒜 as well. 

Now, given a run of the multiset voter model, define a (coupled) run of the two-state voter model with initial state 𝒜 by defining, for every i∈ V and every moment t, A_i to denote the parity of the multiset of opinions from set 𝒜 only held at moment t by vertex i.

Since ℬ is a stabilizing set one can reach parity of opinions on ℬ in the voter model. At that time each opinion (including those in 𝒜) is present an even number of times among nodes in ℬ. Therefore we have parity of opinions on ℬ in the coupled two-state voter model as well. 

 

 In the settings of Theorem <ref> we have, for every t∈ N

    Pr[c_2-VM(H;𝒜,ℬ)>t]≤ Pr[C_VM(H;ℬ)>t], 
    
    E[c_2-VM(H;𝒜,ℬ)]≤ E[C_VM(H;ℬ)]

 
 
The first inequality follows from coupling. For the second we apply Lemma <ref>.
 



We complement the second inequality in the previous corollary by one with the opposite direction, derived as follows: Consider the following process, parameterized by a positive number ϵ > 0, which yields a random model we will call D_ϵ: 
 

  - we partition the vertices of H into two parts, D and D by including each vertex into D independently with probability 1/2-ϵ.    

  - we run the two-state voter model from configuration D (i.e.  0 on labels of vertices of D ("reds") and 1 on vertices of D ("blues")).

  - We denote by D_t the set of vertices labeled 1 at time t, by N_t^D_ϵ the cardinal of D_t,  and by Δ_t^D_ϵ the difference in the number of ones as a result of the (possible) jump at time t. 

  - Denote by C^D_ϵ the smallest time t≥ 0 when N_t^D_ϵ=0. Denote by  c_2-VM^ D_ϵ(H;ℬ) the corresponding parity time. 
 



 For every 0<ϵ<1/2 we have 
    E[c_VM(H;ℬ)]≤2/1-2ϵ· E[C^ D_ϵ_2-VM(H;ℬ)]
 
 


Suppose at time t we do not have parity on ℬ. Let C_t be the resulting configuration.  Let (a_1,a_2,…, a_n) be the vectors of label parities on ℬ of all initial opinions. By our assumption there must be two different opinions v_1,v_2 whose number of copies in C_t|_ℬ have  different parities: a_i≠ a_j.
We next apply the following trivial lemma

 
Conditional on being in state C_t, 

    Prob[∑_k∈ D a_k≡ 1 ]≥ 1/2-ϵ.

 
 If a_i is odd then including/excluding i from D changes the parity of ∑_j∈ D a_j.  
 

As a consequence we infer, similarly to the graph case <cit.>, that 
Prob[c^ D_ϵ_2-VM(H;ℬ)>t]≥(1/2-ϵ) Prob[c_VM(H;ℬ)> t].
Finally, by Lemma <ref> E[c_VM(H;ℬ)]≤2/1-2ϵ· E[C^ D_ϵ_2-VM(H;ℬ)]
 





 §.§ Reachability and recurrence in the two-party voter model on odd-connected hypergraphs


The previous section motivates the study of recurrent states of the two-party voter model. For odd-connected hypergraphs the answer is especially simple:


  Let H be an odd-connected hypergraph and let A be an initial state for the two-party voter model on H. Then the following hold: 
  
 
  (a). If H has an edge e with |e| odd then state 0, in which all nodes have label zero, is reachable from A. 
 
  (b). If all edges e of H have even size then from any state different from 1 the system can reach state 0. State 1 is another fixed point of the system. In this second state we have reached parity on all stabilizing sets ℬ for the annihilating random walk on H. 
 



Consider a state B≠ 0,  1 reachable from A. We will show that there is another state reachable from A with strictly fewer ones than in B. 

Indeed, since B is not an even dominating set, there must exist a hyperedge e of H such that |e∩ B| is odd, in particular is nonzero. Consider the natural configuration 1_B with ones on B and zero outside this set.

  By scheduling a node of B∩ e we reach a configuration 1_C in the two-state voter model with a strictly lower number of ones. This happens, of course, since |B∩ e| is odd.

  Since in the above argument B was an arbitrary subset, it follows that state 0 is reachable in the 2-state voter model from any initial configuration.
  
  The argument also works when B=  1 if hypergraph H has an edge e with |e| odd, since in this case by scheduling edge e one can reach a state different from 1. 
  
 In the second case, let ℬ be a stabilizing state, let B be its support, let w_1 be the vector which is 1 on B and 1 outside of it. Adding all equations of satisfiable system H(w_1,0) we get 
 
    0 = ∑_e∈ E |e|x_e=∑_v∈ V w_1[v]-0[v]= ∑_v∈ B 1,

 so |B| must be even. Therefore in state 1 of the 2-state vector model we have reached parity on any state ℬ. 
 

As a sanity check, let us briefly discuss the implications of the previous result in the case when H is a graph without loops. In this situation the voter model on H reaches unanimity, i.e. one of the opinions will dominate, and all other opinions will dissapear. In this case the two-party voter model will reach state 1 iff its initial state contains a 1 on the winning opinion of the voter model, and state 0 otherwise. 

The previous result has beneficial consequences for the analysis of the voter model (and, equivalently, of the lazy annihilating random walk) on odd-connected hypergraphs: instead of analyzing the  (difficult to control) condition of parity on some stabilizing state ℬ one can instead bound  the weaker condition that the voter model reaches state 0 (or ones of states 0,1 in case (b).) which then implies parity on all stabilizing sets ℬ.


 
Let H be an odd-connected hypergraph. Define 

    T_parity(H,D_ϵ) =min{t≥ 1: D_t=∅},

i.e. the minimum time when model D_ϵ is in configuration 0 if H is in case (a). of Theorem <ref>, and  

    T_parity(H,D_ϵ) =min{t≥ 1: D_t∈{∅,V}},

in case (b). 
 

The previous discussion implies the following result: 


We have 

    C^ D_ϵ_2-VM(H;ℬ)≤ T_parity(H,D_ϵ).






§ UPPERBOUNDING ANNIHILATION TIME OF A.R.W. ON HYPERGRAPHS




In this section we complete the proof our main result. 
It shows that one can extend from graphs to odd-connected hypergraphs the crude upper bounds arising from bottleneck statistics (in the terminology of <cit.>) for the annihilation time of a.r.w. 






 §.§ Spectral measures for hypergraphs
 

The classical definition  of the Cheeger constant of a connected graph is <cit.>: 

    ϕ(G) = min_0 < |A| ≤n/2|E(A,A)|/|A|,

where E(A,A) is the edge boundary of set A, that is, the set of edges with  one endpoint in set A and another one in its complement. In practice a related version is often used: 
 
The edge expansion (or Cheeger constant) h(G) of graph G is defined as

    h(G) = min_0 < |A| < n n|E(A,A)|/|A||A|,
 
 

On the other hand the analysis of voter model on graphs <cit.> required a different variant, related to the conductance of a graph and called in <cit.> Cheeger time:  

 For a k-regular graph G define the Cheeger time τ_G  of G by  τ_G=sup_0<|A|<nk|A||A|/n· |E(A,A)|(=k/h(G))


 


The definitions of Cheeger constant/time has recently been lifted up from graphs to simplicial complexes in several related but different ways: 

  *  First, cohomological (coboundary) versions of Cheeger constant have appeared, implicitly or explicitly, in several works <cit.>: For i≥ 1 the  coboundary expansion in dimension i is defined as  

    ε_i(X)=min_f∈ C^i-1[X,  Z_2]∖ B^i-1[X,  Z_2]|supp(d_if)|/|[f]|

Here C^j[X,  Z_2] is the set of j-cochains on X with values in Z_2, B^j[X,  Z_2] is the set of j-boundaries, d_j:C^j[X,  Z_2]→ C^j+1[X,  Z_2] is the j'th coboundary operator

    d_j[f](x_1,x_2,…, x_j+1)=∑_k=1^j+1f(x_1,x_2,…, x̂_k, …, x_j+1)

and |[f]|=min_ξ∈ C^i-1[X,  Z_2] |supp(f+d_i-1(ξ)|.

  *  On the other hand Parzanchevski et al.<cit.> gave a 
combinatorial extension of the Cheeger constant to simplicial complexes:

    h(X)=min_V=⊔_i=1^k A_in· |F(A_1,A_2,…, A_k)|/|A_1|· |A_2|·…· |A_k|
 
where the minimum is taken over all partitions of V into nonempty subsets A_1,A_2,… A_k and by F(A_1,A_2,…, A_k))
we have denoted the set of (k-1)-dimensional simplices with one vertex in each of A_1,A_2,… A_k (see also the slightly modified version h^'(X) of Gundert and Szedlák <cit.>).
 



§ PROOF OF THEOREM <REF>


Because of the additivity of the two-party voter model it is easy to see that 

    max_𝒜 E[C^ D_2-VM(H;𝒜,ℬ)] = max_i∈ V E[C^ D_2-VM(H;{i},ℬ)]
 
To prove Theorem <ref> (1) and (2) we have to show that we have 

    max_ℬ E[C^ D_ϵ_2-VM(H;ℬ)]
     ≤ T_n(H)
 
for some functionT_n(H)with the properties from Theorem <ref>.

From Lemma (<ref>), all we have to prove is that in factE[T_parity(H,D_ϵ)]≤T_n(H)for a corrresponding functionT_n. 
We first show that  
We have 





    P[Δ N_t^D_ϵ= -1]- P[Δ N_t^D_ϵ= 1]= |E^-(D_t,D_t)|-|E^+(D_t,D_t)|/nk
 
In the two-party voter model. 
N_t^D_ϵ decreases by one exactly when the  chosen vertex v has label 1 and the edge e∋ v contains an odd number of nodes (including v !) with label 1. Similarly, 
N_t^D_ϵ increases by one precisely when the chosen vertex v has label 0 and the edge e∋ v has an odd number of nodes with label 1. The number of distinct vertex-edge pairs in the two-party multiset voter model is precisely kn, since every vertex of H has degree exactly k. The number of vertex-edge pairs that lead to an increase by 1 is  nothing but |E^+(D_t,D_t)|, with E^+ having the meaning from  Definition <ref>. 


We complete the proof of the upper bounds (<ref>) for Cases (i) and (ii) using drift arguments entirely similar to the ones used in the proof of Theorem <ref> (i) and (ii). Instead ofΔu(t)we will controlΔN_t^D_ϵ, and we upper bound the expected time to hit  0, conditional (when Case (b) of Theorem <ref> applies) on not hitting state  1 (if this latter event happens parity is reached). 

 In Case (i) we have positive drift and the expected convergence time will be linear, whereas in Case (ii) we correct the expected running time of the unbiased lazy random walk withτ_odd(D(Φ_n)), due to inequality 
 
    P[Δ N_t^D_ϵ= -1]≥1/τ_odd(D(Φ_n))


All other details are entirely similar.We complete the proof of the upper bound (<ref>) as follows: 


  (i).
First we rewrite drift condition as 
    E[Δ N_t^D_ϵ]=Prob[Δ N_t^D_ϵ= 1]- Prob[Δ N_t^D_ϵ= -1]≤ -δ/k (*)
  Because probabilities above belong to interval (0,1), -1≤ E[Δ N_t^D_ϵ]≤ -δ/k. Also 

    Prob[Δ N_t^D_ϵ= 1]= 1/2[(Prob[Δ N_t^D_ϵ= 1]+ Prob[Δ N_t^D_ϵ= -1])+ 
     (Prob[Δ N_t^D_ϵ= 1] - Prob[Δ N_t^D_ϵ= -1])]≤1/2-δ/2k

and 

    Prob[Δ N_t^D_ϵ= -1]≥  Prob[Δ N_t^D_ϵ= 1]+ δ/k≥δ/k.

  In fact, as long as N_t^D_ϵ>0, Δ N_t^D_ϵ can be stochastically upper bounded by a random variable X_t taking only values -1,0,1 which has  the following properties:
 
  (a).Pr[X_t=0]=Pr[Δ N_t^D_ϵ=0]. 
 
  (b).E[X_t]=Pr[X_t=1]-Pr[X_t=-1]=-δ/k 
 To accomplish this, we simply "move mass" in Δ N_t^D_ϵ from value -1 to +1. There is "enough mass" at -1 because of (*). 

Since hyperedge choices are independent, random variables Δ N_t^D_ϵ are also independent and we can take their dominating random variables X_t  
to be independent too. 

Given arbitrary independent random variables Z_t with values in -1,0,1 and E[Z_t]=-δ/k define 
chain (Y_t) by Y_0=Z_0, Y_t=Y_t-1+ Z_t. By standard application of elementary hitting time techniques (such as the forward equation and generating functions) to chain Y_t 
we infer 

    E_Y_0 [T_{Y_t=0}]=Z_0δ/k.
 Applying this to chain Z_t=Δ N_t^D_ϵ (or, rather to Z_t=Y_t) we infer 

    max_ℬ E[T_parity(H,D_ϵ)] ≤nδ/k:=T_H(n).

  (ii).

The argument is similar: we couple the process with a random walk Y_t on the integers with a reflecting (upper bound) barrier  at n. We do so by requiring that for every 0≤ k< n, Pr[Δ N_t^D=0 | N_t^D_ϵ=k]=Pr[Δ Y_t=0 | Y_t=k], 
and redistributing the remaining probability equally between Pr[Δ Y_t=-1 | Y_t=k] and Pr[Δ Y_t=1 | Y_t=k]. From the hypothesis, N_t^D_ϵ can be stochastically dominated by Y_t, so upper bounds for the maximum hitting time of Y_t upper bound the maximum hitting time of N_t^D_ϵ as well. 

By equality 

    Pr[Δ Y_t=-1 | Y_t=k]=Pr[Δ Y_t=1 | Y_t=k]≥
    ≥1/2·1/τ_odd(H)·k· (n-k)/n.

 Now we apply to chain Y_t Lemma 10 from <cit.>), comparing Y_t with the random walk on the integers, whose maximum hitting time is Θ(n^2) The conclusion is that T(n) can be taken to be O(n^2·τ_odd(H)).  


 

 



 §.§ Application to k-XOR-SAT
 

The result in the previous section applies to a particular class of instances ofk-XOR-SAT: 

 Given satisfiable instance H of k-XOR-SAT, the dual hypergraph D(H) is  odd-connected if and only if there is no proper nonempty subsystem W of H such that every variable in H appears in W an even number of times.
 
Immediate. 
 

We will also call such an instanceHofk-XOR-SAT  odd-connected. 

Putting the last three inequalities together, applying them tok-XOR-SAT and getting back from a continuous to an equivalent discrete time model we get an upper bound on convergence time ofWalkSAT: 

 Given satisfiable, odd-connected instance Φ of k-XOR-SAT, k≥ 3, the following holds: 

    max_A E[WalkSAT(X_0)]≤ 2m^2· T_D(H)(m),

 where m is the number of equations in H and the maximum is taken over all initial assignments X_0. 
 
An easy consequence of the relation between discrete-time Markov chains and their continuous-time counterparts <cit.>, and the fact that |V(D(H))|=m. 
 

§ CONCLUSIONS
 

Our main technical contribution has been to show that the use of hypergraph versions of particle systems renders the problem of analyzing the running time of XOR-SAT solvable via a reduction to drift analysis. 

Our work could naturally be completed in many ways. First of all, we would like to remove some of the technical restrictions on the class of instances that can be analyzed with methods similar to ours. For instance, we would like to remove the condition of unique satisfiability from the statement of Theorem <ref>. The condition of acyclicity of instances of XOR-SAT can probably be removed from the statement of Theorem <ref>. Concerning this result, it would be interesting to also obtain lower bounds on the expected convergence time of WalkSAT in terms of structural properties of the triadic dual. Our method did not allow us to accomplish this goal, as it first replaced annihilating random walks by their lazy versions (that could be coupled to the lazy coalescing random walks, which are dual to the multiset voter model) and then replaced parity in the multiset voter model on the stabilizing setBby a more tractable condition (that yielded an upper bound for its convergence time). 

On the other hand, more sophisticated methods and bounds on coalescence/annihilation, similar to those in <cit.> could perhaps be obtained via further research, and are left as open problems. 

More importantly, it would be interesting to see if the running time of WalkSAT and related local search procedures, can be analyzed on instances more interesting problems (e.gk-SAT) in terms of (suitably defined) "particle systems". 

Last but not least we believe that the explosive models defined in this paper deserve further independent study.  For instance, we would like to understand the structure of recurrent states in coalescing random walk model on hypergraphs when state0is not reachable. Also, the long-term structure of the multiset voter model deserves, we believe, further clarifications, especially in the case (b). of Theorem <ref> which is more similar to the graph case. 

 10achlioptas2015solution
D. Achlioptas and M. Molloy.
 The solution space geometry of random linear equations.
 Random Structures & Algorithms, 46(2):197–231, 2015.

aldous-fill-book
D. Aldous and A. Fill.
 Reversible Markov Chains and Random Walks on Graphs.
 book manuscript, 
  http://www.stat.berkeley.edu/~aldous/RWG/book.html, 2019.

aldous1999deterministic
D. Aldous.
 Deterministic and stochastic models for coalescence (aggregation and
  coagulation): a review of the mean-field theory for probabilists.
 Bernoulli, pp. 3–48, 1999.

alekhnovich2006linear
M. Alekhnovich and E. Ben-Sasson.
 Linear upper bounds for random walk on small density random 3-CNFs.
 SIAM Journal on Computing, 36(5):1248–1263, 2006.

altarelli2008relationship
F. Altarelli, R. Monasson, and F. Zamponi.
 Relationship between clustering and algorithmic phase transitions in
  the random k-XORSAT model and its NP-complete extensions.
 Journal of Physics: Conference Series, 95:
  012013, 2008.

amin1992neighborhood
A.T. Amin and P. J. Slater.
 Neighborhood domination with parity restrictions in graphs.
 Congressus Numerantium, pages 19–19, 1992.

redner-balance
T. Antal, P. L. Krapivsky, and S. Redner.
 Social balance on networks: The dynamics of friendship and enmity.
 Physica D, 224(130), 2006.


doerr-book
A. Auger and B. Doerr (eds.)
Theory of Randomized Search Heuristics World Scientific, 2011. 

avin2014radio
C. Avin, Y. Lando, and Z. Lotker.
 Radio cover time in hypergraphs.
 Ad Hoc Networks, 12:278–290, 2014.

barthel2003solving
W. Barthel, A. K. Hartmann, and M. Weigt.
 Solving satisfiability problems by fluctuations: The dynamics of
  stochastic local search algorithms.
 Physical Review E, 67(6):066104, 2003.

chung2012hypergraph
F. Chung and A. Tsiatas.
 Hypergraph coloring games and voter models.
 Internet Mathematics, 10(1–2):66–86, 2013.

coja2009smoothed
A. Coja-Oghlan, U. Feige, A. Frieze, M. Krivelevich, and D. Vilenchik.
 On smoothed k-CNF formulas and the WalkSAT algorithm.
 In  Proceedings of the Twentieth Annual ACM-SIAM Symposium on
  Discrete Algorithms (SODA'09), pages 451–460. Society for Industrial and Applied
  Mathematics, 2009.

walksat-stalls
A. Coja-Oghlan, A. Haqshenas, and Samuel Hetterich.  Walksat Stalls Well Below Satisfiability.
 SIAM Journal on Discrete Mathematics 31(2): (2017): 1160-1173.

coja2012analyzing-journal
A. Coja-Oghlan and A. M. Frieze.
 Analyzing WalkSAT on random formulas.
SIAM Journal on Computing, 45(14):1456–1485, 2014.

cooper2013coalescing
C. Cooper, R. Elsa̋sser, H. Ono, and T. Radzik.
 Coalescing random walks and voting on connected graphs.
 SIAM Journal on Discrete Mathematics, 27(4):1748–1758, 2013.

cooper2013cover
C. Cooper, A. Frieze, and T. Radzik.
 The cover times of random walks on random uniform hypergraphs.
 Theoretical Computer Science, 509:51–69, 2013.

cooper2012spectra
J. Cooper and A. Duttle.
 Spectra of uniform hypergraphs.
 Linear Algebra and its Applications, 436(9):3268–3292, 2012.

cooper2016linear
C. Cooper, Colin and N. Rivera. 
 The linear voting model. 
 In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.

donnelly-welsh-interacting
P. Donnelly and D. Welsh.
 Finite particle systems and infection models.
 Math.Proc. Cambridge Philos.Soc., 94:167–182, 1983.

donnelly-welsh-coloring
P. Donnelly and D. Welsh.
 The antivoter problem: Random 2-colorings of graphs.
 In B. Bollobás, editor,  Graph Theory and Combinatorics,
  pages 133–144. Academic Press, 1984.

droste2002analysis
S. Droste, T. Jansen, and I. Wegener.
 On the analysis of the (1+ 1) evolutionary algorithm.
 Theoretical Computer Science, 276(1):51–81, 2002.

guidetti2011walksat
M. Guidetti and A.P. Young. 
 Complexity of several constraint-satisfaction problems using the heuristic classical algorithm WalkSAT. 
 Physical Review E 84.1 (2011): 011102.


he2001drift
J. He and X. Yao.
 Drift analysis and average time complexity of evolutionary
  algorithms.
 Artificial Intelligence, 127(1):57–85, 2001.

random-lights-out
J.T. Hughes.
 Random lights-out processes on graphs.
 Advances in Applied Mathematics, 51(2):254–265, 2013.

ibrahimi2012set
M. Ibrahimi, Y. Kanoria, M. Kraning, and A. Montanari.
 The set of solutions of random XORSAT formulae.
 In  Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on
  Discrete Algorithms (SODA'12), pages 760–779. Society for Industrial and Applied Mathematics, 2012.

istrate-balance
G. Istrate.
 On the dynamics of social balance on general networks (with an
  application to XOR-SAT).
 Fundamenta Informaticae, 91(2):341–356, 2009.

aimath04
G. Istrate, A. Percus, and S. Boettcher.
 Spines of random constraint satisfaction problems: Definition and
  connection with computational complexity.
 Annals of Mathematics and Artificial Intelligence,
  44(4):353–372, 2005.

istrate2015reachability
G. Istrate.
 Reachability and recurrence in a modular generalization of
  annihilating random walks (and lights-out games) to hypergraphs.
 Theoretical Computer Science, 580:83–93, 2015.
 kanade
V. Kanade, F. Mallmann-Trenn, and T. Sauerwald. 
 On coalescence time in graphs: When is coalescing as fast as meeting?.
 In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'19), pp. 956-965. Society for Industrial and Applied Mathematics, 2019.

lehre2014concentrated
P. K. Lehre and C. Witt.
 Concentrated hitting times of randomized search heuristics with
  variable drift.
 In  Algorithms and Computation, pages 686–697. Springer, 2014.

liggett-ips
T. Liggett.
 Interacting Particle Systems.
 Springer Verlag, 2004.

lu2012loose
L. Lu and X. Peng.
 Loose laplacian spectra of random hypergraphs.
 Random Structures & Algorithms, 41(4):521–545, 2012.

oliveto2011simplified
P. S Oliveto and C. Witt.
 Simplified drift analysis for proving lower bounds in evolutionary
  computation.
 Algorithmica, 59(3):369–386, 2011.

papadimitriou1991selecting
C. Papadimitriou.
 On selecting a satisfying truth assignment.
 In   Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS'91), pages 163–169. IEEE, 1991.

parzanchevski2012isoperimetric
O. Parzanchevski, R. Rosenthal, and R.J. Tessler.
 Isoperimetric inequalities in simplicial complexes.
Combinatorica 36.2 (2016): 195-227.

triad-xorsat
F. Radicchi, D. Vilone, S. Yoon, and H. Meyer-Ortmanns.
 Social balance as a satisfiability problem of computer science.
 Physical Review E, 026106, 2006.

scherphuis-lightsout
J. Scherphuis.
 The mathematics of lights out.
 Web page, http://www.jaapsch.net/puzzles/lomath.htm, 2019.

schoning1999probabilistic
T Schőning.
 A probabilistic algorithm for k-SAT and constraint satisfaction
  problems.
 In  Proceedings of the 40th Annual Symposium
  on Foundations of Computer Science (FOCS'99), pages 410–414. IEEE, 1999.

walksat
B. Selman, H. Kautz, and B. Cohen. 
 Local search strategies for satisfiability testing.  In  Cliques, coloring, and satisfiability, DIMACS Series in Theoretical Computer Science, vol. 26 (1993): 521-532.

semerjian2003relaxation
G. Semerjian and R. Monasson.
 Relaxation and metastability in a local search procedure for the
  random satisfiability problem.
 Physical Review E, 67(6):066103, 2003.

semerjian2004study
G. Semerjian and R. Monasson.
 A study of pure random walk on random satisfiability problems with "physical" methods. 
 In  Theory and Applications of Satisfiability Testing, pages
  120–134. Springer, 2004.

steenbergen2012cheeger
J. Steenbergen, C. Klivans, and S. Mukherjee.
 A Cheeger-type inequality on simplicial complexes.
Advances in Applied Mathematics 56 (2014): 56-77.


sutner-lightsout
K. Sutner.
 Linear cellular automata and the Garden-of-Eden.
 The Mathematical Intelligencer, 11:49–53, 1989.

zhou2013exponential
Y-R. Zhou.
 Exponential bounds for the random walk algorithm on random planted
  3-SAT.
 Science China Information Sciences, 56(9):1–13, 2013.



§ PROOF OF LEMMA <REF>


§ EXAMPLES: ODD CHEEGER DRIFT
 

§ COUNTEREXAMPLES FOR REACHABILITY
 

We give two types of counterexamples. The first one is the setting for which a partial converse was (incorrectly) claimed in <cit.>: 
connected hypergraphs without graph edges. 

The second counterexample shows that the failure of the converse implication is not specific to hypergraphs: even on graphs the sufficient condition fails to be necessary.  





 
There exist

  (a). 
a connected hypergraph H that contains no graph edges,
and

  (b).  a connected graph (i.e. all hyperedges have size two) H,   

as well as two configurations w_1,w_2 on H such that system H(w_1,w_2) has solutions in Z_2, yet w_2 is not reachable in H from w_1. 





  *  


Let H be a hypergraph consisting of three hyperedges e_1,e_2,e_3 sharing a common vertex (Figure <ref>). Let w_1, w_2 be the configuration described in that figure: the private vertices of e_2 (displayed with a solid line in Figure <ref>) have initial value 1 in w_1, 
all other vertices being 0. On the other hand w_2 takes value 0 on the shared vertex and 1 everywhere else. 

It is easy to see that system H(w_1,w_2) has a solution z with z(e_1)=z(e_3)=1 and z(e_2)=0. Yet w_2 is not reachable from w_1. Indeed hyperedges with three labels of one have no preimage. So the only preimages of state w_2 are itself and the three ones obtained by flipping labels on one hyperedge. 

  *  


Let H be the complete graph K_4 and let w_1 be 1 at a single vertex v (Figure <ref>). Let w_2 be the configuration with ones at  every vertex but v. System H(w_1,w_2) has solution z_e=1 for every edge e, yet 
w_2 is  not reachable from w_1, as w_1 has a single one and w_2 has three, but on a graph the number of ones does not increase. 





§ EXAMPLES


§ COUPLING PROOF
 

We will define the following stochastic processP: 


  *  Initial state:A_i={(i,∞)} for i∈ℬ, A_i=∅ otherwise. Note that A_1∪ A_2∪…∪ A_n=ℬ×{∞} and that each A_i contains at most one index b_i with (b_i,∞)∈ A_i. We will call such a multiset  live and b_i the witness for A_i. Also denote B_i=A_i∖{(i,∞)} if i is live, B_i=A_i otherwise. 

  *  Move: At time t: Choose  random vertex i (not necessarily live). Choose random edge (i,j_1,…, j_k). For r=1,…, k
  *  If both A_i,A_j_r are live then make A_j_r= (B_i⊔ B_j_r)⊔{(b_i,t),(b_j_r,t)}.

  *  If, on the other hand,  at most one of A_i,A_j_r is live then make A_j:=A_i⊔ A_j_r. 
 
Finally make A_i=∅. Note that if we "move" a dead set A_i to a live multiset A_j then A_j will still be live. 

  *  Stopping: Stopping time c_P(G) is the minimum t≥ 0 such that at most one i is live (one if n is odd, none if n is even)
 The following are true: 

  * P observed on [n]×{∞}  and moves of live multisets only is the annihilating random walk on G starting from configuration ℬ.  If n is even then at time c_P(G) all particles have annihilated. Consequently c_ann(G, ℬ)≤ c_P(G, ℬ). 

  * P where we disregard second components in all pairs is identical to the coalescing random walk on G and
c_P(G, ℬ)=c_coal(G,ℬ). 
 

A "proof by picture" is given in Figure <ref>. There are two cases:jis live or not. In both cases the observed process is identical to the annihilating random walk. Note that ifnis even then when coalescence occurs in the c.r.w. all particles have died in the a.r.w.




§ PROOF OF THEOREM <REF>

 


§ LEMMA <REF> (A): AN INDEPENDENT PROOF

First we rewrite drift condition as
E[ΔN_t^D]=Prob[ΔN_t^D= 1]- Prob[ΔN_t^D= -1]≤-δ/k.Because probabilities above belong to interval (0,1),-1≤E[ΔN_t^D]≤-δ/k, henceδ≤k. Also
Prob[ΔN_t^D= 1]= 1/2[(Prob[ΔN_t^D= 1]+ Prob[ΔN_t^D= -1])+(Prob[ΔN_t^D= 1]- Prob[ΔN_t^D= -1])]≤1/2-δ/2kandProb[ΔN_t^D= -1]≥Prob[ΔN_t^D= 1]+ δ/k≥δ/k.In fact, as long asN_t^D>0,ΔN_t^Dcan be stochastically upper bounded by a random variableX_ttaking value0with the same probability asΔN_t^D, and such thatE[X_t]=-δ/k. 

Since hyperedge choices are independent, random variablesΔN_t^Dare also independent and we can take their dominating random variablesX_tto be independent too. 

Given arbitrary independent random variablesZ_twith values in-1,0,1andE[Z_t]=-δ/kdefine 
chain(Y_t)byY_0=Z_0,Y_t=Y_t-1+ Z_t. By standard application of elementary hitting time techniques (such as the forward equation and generating functions) to chainY_twe inferE_Y_0 [T_{Y_t=0}]=X_0δ/k.Applying this to chainN_t^Dwe infer
max_ℬ E[C^D_ϵ_2-VM(H;ℬ)] ≤nδ/k.We now apply the following result (<cit.> Theorem 1.3 pp. 15):


 Let g: R_+ R_+ be a monotone nondecreasing function. Consider a particle whose position changes at integer moments and is always an integer. If the particle is at position m>1, it proceeds at the next step to position m-X, where X is a random variable ranging over the integers 1, …, m-1. All we know about X is that E[X]≥ g(m) and that X is chosen independently of the past.

Let T be the random variable denoting the number of steps in which the particle reaches position 1. Then E[T]≤∫_1^ndx/g(x).