Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem

The $k$-XORSAT problem is a Boolean constraint satisfaction problem and closely related to the well-known $k$-SAT problem. An instance $\Phi$ of the $k$-XORSAT problem consists of $m$ clauses in $n$ Boolean variables. Each clause is a Boolean linear equation of $k$ variables of the form $x_{j_{1}}\oplus x_{j_{2}}\oplus\cdots\oplus x_{j_{k}}=b_{j}$, where $\oplus$ is the modulo-2 addition. By convention, when we say an XORSAT instance, without the prefix ”$k$”, we mean the same except we do not require the clauses to have exactly $k$ variables. An assignment $\sigma$ to the $n$ variables is a mapping from the set $\{x_{i}:i\in[n]\}$ of all $n$ variables to the set $\{0,1\}$ of the two Boolean values. By abusing the notation, we can write it as the Boolean vector $\sigma=(\sigma(x_{1}),\sigma(x_{2}),\cdots,\sigma(x_{n}))\in\{0,1\}^{n}$ containing the assigned values. The distance $d(\sigma,\sigma^{\prime})$ between any two assignments $\sigma$ and $\sigma^{\prime}$ is defined to be the Hamming distance $d(\sigma,\sigma^{\prime})=\sum_{i=1}^{n}\mathbbm{1}(\sigma(x_{i})\neq\sigma^{\prime}(x_{i}))$. A clause is satisfied by an assignment if the equation of the clause holds when the variables are replaced by the corresponding assigned values, and an instance of the $k$-XORSAT problem is satisfied by an assignment if all its clauses are satisfied by the assignment. An instance is satisfiable if it has at least one satisfying assignment, or unsatisfiable if it does not have any satisfying assignment. The assignment $\sigma$ that satisfies the instance $\Phi$ is called a solution for the instance. The set of all satisfying solutions for the instance $\Phi$ is called the solution space of the instance, denoted by $\mathcal{S}(\Phi)$. We are interested in the complexity of finding a solution.

Since each clause is just a Boolean linear equation, an instance $\Phi$ can be viewed as a Boolean linear system $Ax=b$, where $A\in\{0,1\}^{m\times n}$ is an $m\times n$ Boolean matrix and $b\in\{0,1\}^{n}$ is a vector of length $n$. Note that each row in $A$ contains exactly $k$ ones, since each clause has exactly $k$ variables. We can see that finding solutions for a $k$-XORSAT instance is equivalent to solving a Boolean linear system, and the solution space $\mathcal{S}(\Phi)$ is an affine space inside $\{0,1\}^{n}$. By abusing the notation, we can simply write $\Phi=(A,b)$, and the terms ”clause” and ”equation” are interchangeable here.

We are particularly interested in random instances of the $k$-XORSAT problem. In a random instance $\mathbf{\Phi}$, each clause is drawn over all $2\binom{n}{k}$ possibilities, independently. In particular, the left-hand side of the equation is the modulo-2 sum of $k$ variables chosen uniformly from $\binom{n}{k}$ possibilities, and the right-hand side is either 0 or 1 with even probabilities. Therefore, a random instance $\mathbf{\Phi}$ of the $k$-XORSAT problem is drawn uniformly from the ensemble $\mathbf{\Phi}_{k}(n,m)$ of all possible instances of the $k$-XORSAT problem with $n$ variables and $m$ clauses, each clause containing exactly $k$ variables, and we denote this by $\mathbf{\Phi}\sim\mathbf{\Phi}_{k}(n,m)$. We focus on the regime in which the number of variables $n$ goes to the infinity and the number of clauses $m$ is proportional to the number of variables $n$, that is, $m=rn$, where $r$ is a constant independent of $n$ and called the clause density.

Since a $k$-XORSAT instance can be represented by a system of linear equations in $G\mathbb{F}(2)$, given an instance, some standard linear algebra methods such as the Gaussian elimination can determine whether the instance is satisfiable, find a solution, and even count the total number of solutions, in polynomial time. However, beyond this particular algebraic structure, some variants of the $k$-XORSAT problem is hard to solve. Achlioptas and Molloy mentioned in their paper [AM15] that random instances of the $k$-XORSAT problem seems to be extremely difficult for both generic CSP solvers and SAT solvers, which do not take the algebraic structure into account. Guidetti and Young [GY11] suggested that the random $k$-XORSAT is the most difficult for random walk type algorithms such as WalkSAT, among many random CSPs. The difficulty of solving random $k$-XORSAT instances becomes more apparent when we only consider linear-time algorithms as efficient algorithms, since we do not have linear-time algebraic method to solve a linear system in general.

Many studies suggest that the difficulties of solving random CSPs are related to the phase transition of the solution spaces when the clause density $r$ grows. (We will have more detailed discussion in Section 1.3.) Pittel and Sorkin [PS16] obtained the sharp satisfiability threshold $r_{sat}(k)$ of random $k$-XORSAT, for general $k\geq 3$: The random $k$-XORSAT instance is satisfiable w.h.p. when $r<r_{sat}(k)$, and it is unsatisfiable w.h.p. when $r>r_{sat}(k)$. (We say an event $\mathcal{E}_{n}$, depending on a number $n$, occurs with high probability, or shortened to w.h.p., if the probability of the event $\mathcal{E}_{n}$ occurring converges to 1 as $n$ goes to the infinity, that is, $\lim_{n\rightarrow\infty}\Pr\left[\,{\mathcal{E}_{n}}\,\right]=1$.) Furthermore, Ibrahimi, Kanoria, Kraning and Montanari [IKKM12] obtained the sharp clustering threshold $r_{core}(k)$, which is less than $r_{sat}(k)$, of random $k$-XORSAT for $k\geq 3$. When $r<r_{core}(k)$, w.h.p. the solution space of a random $k$-XORSAT instance is ”well-connected”. When $r_{core}(k)<r<r_{sat}(k)$, w.h.p. the solution space of a random $k$-XORSAT instance shatters into an exponential number of ”well-separated clusters”. In [IKKM12], They also provided a linear-time algorithm that can solve a random $k$-XORSAT instance w.h.p. for $r<r_{core}(k)$. On the other hand, no algorithm is known to be able to find a solution for a random $k$-XORSAT instance with non-vanishing probability in linear time, for $r_{core}(k)<r<r_{sat}(k)$ in which solutions exist with high probability.

In this work, we consider a natural class of algorithms, called sequential local algorithms. A sequential algorithm selects an unassigned variable randomly and assigns a value to it, iteratively, until every variable has an assigned value. In each iteration of the algorithm, to decide the assigned value, the algorithm runs some heuristic called local rules which return a value $p\in[0,1]$, and decide the assigned value to be either 0 or 1 randomly, according to the Bernoulli distribution with parameter $p$. Ideally, if in each iteration the local rule can calculate the exact marginal probability of the selected variable over a randomly chosen solution for the instance conditioned on fixing all previously selected variables to their assigned values, the algorithm should be able to find a solution. However, we restrict the ability of the local rules by only providing local structure to the local rules. To explain the meaning of ”local”, we first construct a graphical representation for the $k$-XORSAT instances: the factor graph. The factor graph $G$ of a $k$-XORSAT instance $\Phi$ is constructed in the following way: (1) each variable is represented by a variable node; (2) each equation is represented by an equation node; (3) add an undirected edge $(v,e)$ if the variable $v$ is involved in the equation $e$. Note that since there is a one-to-one correspondence between variables (equations) and variable nodes (equation nodes), in this paper, the terms variables (equations) and variable nodes (equation nodes) are interchangeable. The distance between any two nodes is the number of edges in the shortest path connecting the two nodes. For any integer $R\geq 0$, the local neighborhood $B_{G}(v,R)$ with radius $R$ of a node $v$ is the subgraph of $G$ induced by all nodes with distances less than or equal to $R$ from the node $v$. By ”local” in the name of the algorithms, it means the local rules only takes the local neighborhood of the selected variable, of radius $R$, as its input.

The actual implementation of a sequential local algorithm depends on the choice for the local rules. To emphasize the choices for the local rules of the algorithms, the sequential local algorithm with the given local rule $\tau$ is called the $\tau$-decimation algorithm DEC_$\tau$. The formal definitions of the sequential local algorithms, as well as the $\tau$-decimation algorithms, will be given in Section 1.4. Note that if the local rule $\tau$ takes constant time, then the $\tau$-decimation algorithm also takes linear time.

We introduce a notion of freeness to the sequential local algorithms. For any iteration in which the local rule returns $1/2$, we call it a free step. Intuitively, a free step means the local rule cannot obtain useful information from the local structure and let the algorithms make a random guess for the assigned value. We say a $\tau$-decimation algorithm is $\delta$-free if w.h.p. it has at least $\delta n$ free steps. Moreover, we say a $\tau$-decimation algorithm is strictly $\delta$-free if it is $\delta^{\prime}$-free for some $\delta^{\prime}>\delta$. If the $\tau$-decimation algorithm is $\delta$-free with large $\delta>0$, it means the algorithm makes a lot of random guess on the assigned values, and it is likely that the local rule $\tau$ cannot extract useful information from the local structure to guide the algorithm. This leads to our contribution described in the next section.

The main contribution of this work consists of two parts. The first part is to show that as $n\rightarrow\infty$ if the $\tau$-decimation algorithm is strictly $2\mu(k,r)$-free then w.h.p. it fails to find a solution for the random $k$-XORSAT instance, when the clause density $r$ is beyond the clustering threshold $r_{core}(k)$ but below the satisfiability threshold $r_{sat}(k)$. This can be formally written as Theorem 1. The value $\mu(k,r)$ given in Theorem 1 is an upper bound of the number of variables removed from the instance in order to obtain the sub-instance called core instance, which is crucial in our proof. We will discuss its meaning in detail in Section 2.

The best known linear algorithm of finding a solution for the random $k$-XORSAT instance succeeds w.h.p., for $k\geq 3$ and $r<r_{core}(k)$ [IKKM12]. That means these sequential local algorithms do not outperform the best known linear algorithm. Note that $r_{core}(k)$ is where the best known linear algorithm succeeds up to, and where the sequential local algorithms starts failing. These support the intuition that $r_{core}(k)$ is the sharp threshold of the existence of a linear-time algorithm for random $k$-XORSAT problem.

The second part of our contribution is to verify that the ”freeness” condition in Theorem 1 is satisfied by the $\tau$-decimation algorithm with certain local rules $\tau$. One of them is the simplest local rule, the Unit Clause Propagation UC, which tries to satisfy the unit clause on the selected variable if exists, or make random guess otherwise. By using the Wormald’s method of differential equations to count the number of free steps run by UC-decimation algorithm DEC_UC, we can show that it is strictly $2\mu(k,r)$-free on the random $k$-XORSAT instance $\mathbf{\Phi}$ for $k\geq 9$, which leads to the following theorem.

In each iteration, the role of the local rules is to calculate the marginal probability of the selected variable in the instance conditioned on fixing all previously selected variables to their assigned values. Belief Propagation BP and Survey Propagation SP are surprisingly good at approximating marginal probabilities of variables over randomly chosen solutions in many random constraint satisfaction problems empirically [MPZ02, GS02, BMZ05, RS09, KSS09]. In particular, it is well-known that they can calculate the exact marginal probabilities of variables when the underlying factor graph is a tree, which is proved analytically. If Belief Propagation BP and Survey Propagation SP are used as the local rule $\tau$, it is natural to expect that the $\tau$-decimation algorithm can find a solution. However, we prove that even the local rule $\tau$ can give the exact marginal probabilities of variables over a randomly chosen solution for any instance whose factor graph is a tree, the $\tau$-decimation algorithm still cannot find a solution w.h.p. for $k\geq 13$. We know that w.h.p. the local neighborhood of the factor graph of the random $k$-XORSAT instance is a tree. Therefore, running BP and SP on the local neighborhood actually gives the exact marginal probabilities of the selected variables, with respect to the sub-instance induced by the local neighborhood. This implies that both BP-decimation algorithm DEC_BP and SP-decimation algorithm DEC_SP fail to find a solution w.h.p. for $k\geq 13$.

To prove Theorem 2 and Theorem 3, we only need to calculate the number of free steps in DEC_UC and the number of free steps in DEC_$\tau$ with the assumption on $\tau$ described in Theorem 3. If the number of free steps is strictly greater than $2\mu(k,r)n$ with high probability, we know that they are strictly $2\mu(k,r)$-free, and the results follow immediately by applying Theorem 1. Similarly, to obtain the same results for other $\tau$-decimation algorithms, all we need to do is to calculate the number of free steps for those algorithms. If they are strictly $2\mu(k,r)$-free, we can obtain the same results by applying Theorem 1. Note that, due to certain limitations of our calculation, our results are limited to $k\geq 9$ in Theorem 2 and $k\geq 13$ in Theorem 3. We believe that the results hold for general $k\geq 3$, and can be proved by improving some subtle calculation in our argument.

Although we only show a few of implementations of the sequential local algorithms, we believe that the results are general across many sequential local algorithms with different local rules due to Theorem 3. In the framework of sequential local algorithms, the role of the local rules is to approximate the marginal probabilities of the selected variables over a random solution for the instance induced by the local neighborhood centered at the selected variables. Therefore, we believe that for any local rule that can make a good approximation on the marginals, it shall give similar results as Theorem 3. (Note that a more general definition of ”$\delta$-free” may be useful, for example, we can say a $\tau$-decimation algorithm is $(\delta,\epsilon)$-free if we have $|p-1/2|<\epsilon$, where $p$ is the value returned by the local rule, for at least $\delta n$ iterations.)

It is worth to mention the differences between these implementations of the sequential local algorithms and their well-known variants. Firstly, the UC-decimation algorithm is slightly different from the well-known Unit Clause algorithm. Under the framework of sequential local algorithm, the variables are selected in a random order. However, in the well-studied Unit Clause algorithm the variables in unit clauses are selected first [AKKT02]. The difference in the variable order could be crucial to the effectiveness of the Unit Clause algorithm. Secondly, the BP-decimation algorithm and the SP-decimation algorithm are slightly different from the Belief Propagation Guided Decimation Algorithm [Coj17] and Survey Propagation Decimation Algorithm [BZ04, BMZ05, MMW07]. In the framework of sequential local algorithms, we only provide the local neighborhood to BP and SP. It is equivalent to bounding the number of messages passed in each decimation step by the constant $R\geq 0$ in BP-guided Decimation Algorithm and SP-guided Decimation Algorithm. It is in contrast to many empirical studies of BP-guided Decimation Algorithm and SP-guided Decimation Algorithm which allow the message passing iteration to continue until it converges.

Moreover, this work provides a new variant of the overlap gap property method, which was originally introduced by Gamarnik and Sudan [GS17b]. Instead of considering the overlap gap property of the whole instance, we utilize that property of a sub-instance of the random $k$-XORSAT instance. In particular, the proof of this work is inspired by [GS17b], which uses the overlap gap property method to rule out the class of balanced sequential local algorithms from being able to solve random NAE-$k$-SAT problem when the clause density is close to the satisfiability threshold. Instead of directly applying the method on the whole instance, we focus on the sub-instance induced by the 2-core of the factor graph of the instance. This modification help us obtain tight bounds of algorithmic threshold unlike [GS17b]. If we apply the original overlap gap property method and use the first moment method to obtain the property, we are able to show that the sequential local algorithms fail to solve the random $k$-XORSAT problem when the clause density is lower than a certain threshold $r_{1}(k)$. However, that threshold $r_{1}(k)$ is much higher than the $r_{core}(k)$. It only tells us that the algorithms fails when the density is very close to the satisfiability threshold $r_{sat}(k)$. With our modification, we can lower that threshold to exactly $r_{core}(k)$, namely, the algorithms fail in finding a solution when the clause density is as low as the clustering threshold. This opens a new possibility to improve other results which use the overlap gap property method on other random constraint satisfaction problems.

Many random ensembles of constraint satisfaction problems CSPs such as random $k$-SAT and random NAE-$k$-SAT are closely related to the random $k$-XORSAT. For example, the well-known random $k$-SAT is analogous to the random $k$-XORSAT, in the sense that we can obtain a $k$-XORSAT instance from a $k$-SAT instance by replacing OR operators with XOR operators. We are particularly interested in the existences of some sharp thresholds on the clause density $r$ in which the behaviors of a random instance changes sharply when the clause density $r$ grows and passes through those thresholds. The following three thresholds are particularly of interest.

1. 1.

   The satisfiability threshold separates the regime where w.h.p. the random instance is satisfiable and the regime where w.h.p. it is unsatisfiable.

2. 2.

   The clustering threshold separates the regime where w.h.p. the solution space can be partitioned into well-separated subsets, each containing an exponential small fraction of solutions, and the regime where w.h.p. the solution space cannot be partitioned in this way.

3. 3.

   The algorithmic threshold separates the regime where we have an efficient algorithm that can find a solution for a satisfiable random instance with non-vanishing probability, and the regime where no such algorithm exists.

Many random constraint satisfaction problems such as random $k$-SAT, random NAE-$k$-SAT and random graph coloring share the following phenomena related to these thresholds [AC08].

• •

  There is an upper bound of the (conjectured) satisfiability threshold.

• •

  There is a lower bound of the (conjectured) satisfiability threshold, from the non-constructive proof, and the lower bound is essentially tight.

• •

  There are some polynomial time algorithms that can find a solution when the density is relatively low, but no polynomial time algorithm is known to succeed when the density is close to the satisfiability threshold. This leads to a conjectured algorithmic threshold, which is asymptotically below the (conjectured) satisfiability threshold.

• •

  The clustering phenomenon takes place when the density is greater than a (conjectured) clustering threshold, and this threshold is close to or even asymptotically equal to the algorithmic threshold.

It is worth to mention that not every random constraint satisfaction problems share this set of phenomena. The most notable example is symmetric binary perceptron (SBP). Its satisfiability threshold $\alpha_{sat}(k)>0$ was established by [PX21, ALS22b]. They also showed that SBP exhibits clustering property and almost all clusters are singletons, for clause density $\alpha>0$. On the other hand, [ALS22a] gave a polynomial-time algorithm that can find solutions w.h.p., for low clause density. Therefore, there is a regime of low clause density in which SBP exhibits clustering property, and it is solvable in polynomial time, simultaneously. Its clustering phenomenon does not cause the hardness.

Being analogous to the random $k$-SAT problem, the random $k$-XORSAT problem shares those phenomena with other random constraint satisfaction problems. However, the story is slightly different in the random $k$-XORSAT problem. Since the $k$-XORSAT instances are equivalent to Boolean linear systems, their solution spaces are simply some affine subspaces in the Hamming hypercube $\{0,1\}^{n}$. Because of their algebraic structures, we are able to obtain the existence and the ($n$-independent) value of the satisfiability threshold of the random $k$-XORSAT problem. Dubois and Mandler [DM02] proved that there exists an $n$-independent satisfiability threshold $r_{sat}(k)$ for $k=3$, and determined the exact value of the sharp threshold by the second moment argument. Pittel and Sorkin [PS16] further extended it for general $k\geq 3$. An independent work on cuckoo hashing from [DGM⁺10] also included an argument of the $k$-XORSAT satisfiability threshold for general $k\geq 3$. Those proofs consider the 2-core of the hypergraph associated with the random $k$-XORSAT instance. (In graph theory, a $k$-core of a (hyper)graph is a maximal subgraph in which all vertices have degree at least $k$.) Based on the 2-core, we can construct a sub-instance, called 2-core instance or simply core instance of the original instance. One can prove that the original instance is satisfiable if and only if core instance is satisfiable. [CDMM03, MRZ03] studied the core instance and determined the satisfiability threshold of the core instance, which can be converted to the satisfiability threshold of the random $k$-XORSAT instance.

Mézard, Ricci-Tersenghi and Zecchina [MRZ03] started the study of the clustering phenomenon of random $k$-XORSAT, and linked it to the existence of the non-empty 2-core instance. From [PSW96, Mol05, Kim04], we know the non-empty 2-core of random hypergraphs suddenly emerges at a critical edge density $r_{core}(k)$. After that, Ibrahimi, Kanoria, Kraning and Montanari [IKKM12], and Achlioptas and Molloy [AM15] independently proved that there exists the clustering threshold $r_{clt}(k)$, which is equal to $r_{core}(k)$ and smaller than $r_{sat}(k)$, such that w.h.p. the solution space is a connected component for density $r<r_{core}(k)$, and w.h.p. the solution space shatters into exponentially many $\Theta(n)$-separated components for density $r>r_{core}(k)$, provided that we consider the solution space as a graph in which we add an edge between two solutions if their Hamming distance is $O(\log n)$.

As we mentioned before, the random $k$-XORSAT instance can be written as a random Boolean linear system, so it can be solved in polynomial time by using linear algebra method, regardless the clause density. For example, Gaussian elimination can solve it in $O(n^{3})$ time. Since we do not have linear time algebraic method to solve linear system, we can still study the algorithmic phase transition if we only consider linear-time algorithms as efficient algorithms. In the proofs in [IKKM12], they provided an algorithm that can find a solution in linear time when $r<r_{core}(k)$, which implies that $r_{core}(k)$ is a lower bound of the (linear-time version of) algorithmic threshold $r_{alg}(k)$ of the random $k$-XORSAT problem. We conjecture that no algorithm can solve the random $k$-XORSAT problem in linear time with non-vanishing probability when $r>r_{core}(k)$, which implies $r_{core}(k)$ is an upper bound of $r_{alg}(k)$ and thus $r_{alg}(k)=r_{core}(k)$. This would lead to the intimate relation between the failure of linear time algorithms on random $k$-XORSAT and the clustering phenomenon of its solution space.

Sequential local algorithms are a class of algorithms parametrized by a local rule $\tau$ that specifies how values should be assigned to variables based on the ”neighborhoods” of the variables. Given a local rule $\tau$, the sequential local algorithm can be written as the following $\tau$-decimation algorithm.

Given a fixed even number $R\geq 0$, we denote by $\mathcal{I}_{R}$ the set of all instances in which each of those instances has exactly one of its variables selected as root, and all nodes in its factor graph have distances from the root variable node at most $R$. A local rule is defined to be a function $\tau:\mathcal{I}_{R}\rightarrow[0,1]\in\mathbb{R}$, mapping from $\mathcal{I}_{R}$ to the interval $[0,1]$. Given an instance $\Phi$, since the local neighborhood $B_{\Phi}(x^{*},R)$ of a variable node $x^{*}$ represents a sub-instance of $\Phi$ induced by all nodes having distance at most $R$ from the root variable node $x^{*}$, we have $B_{\Phi}(x^{*},R)\in\mathcal{I}_{R}$ and $\tau(B_{\Phi}(x^{*},R))$ is well-defined. Then, the $\tau$-decimation algorithm can be expressed as the followings.

For any $t\in[n]$, if the value $\tau(B_{\Phi_{t}}(x^{*},R))$ given by the local rule $\tau$ in the $t$-th iteration is $1/2$, then we call that iteration a free step. In a free step, the $\tau$-decimation algorithm simply assigns a uniformly random Boolean value to the selected variable. On the contrary, if the value $\tau(B_{\Phi_{t}}(x^{*},R))$ given by the local rule $\tau$ in the $t$-th iteration is either 0 or 1, then we call that iteration a forced step. In a forced step, the $\tau$-decimation algorithm is forced to assign a particular value to the selected variable according to the value $\tau(B_{\Phi_{t}}(x^{*},R))$. To simplify our discussion, we introduce the following definitions for those $\tau$-decimation algorithms having certain numbers of free steps.

There are many choices for the local rules $\tau$. The simplest one is the Unit Clause Propagation UC. In each iteration, after selecting the unassigned variable $x^{*}$, UC checks whether there exists a unit clause (clause with one variable) on the variable $x^{*}$. If yes, then UC sets $\tau(B_{\Phi_{t}}(x^{*},R))$ to be the right-hand-side value of the unit clause, which can force the decimation algorithm to pick the suitable value to satisfy that clause. In this case, this iteration is a forced step. (If there are multiple unit clauses on the selected variable $x^{*}$, then only consider the one with the lowest index.) If there is no unit clause on the selected variable $x^{*}$, then UC sets $\tau(B_{\Phi_{t}}(x^{*},R))$ to $1/2$, which let the algorithm choose the assigned value randomly. In this case, this iteration is a free step.

A new challenger to break the algorithmic threshold came out from statistical mechanics. In experiments [MPZ02, GS02, BMZ05, RS09, KSS09], the message passing algorithms demonstrated their high efficiency on finding solutions of random $k$-SAT problem with the densities close to the satisfiability threshold. Those algorithms include Belief Propagation Guided Decimation Algorithm and Survey Propagation Guided Decimation Algorithm, which are based on the insightful but non-rigorous cavity method from statistical mechanics [BMZ05, RS09]. Unfortunately, several analyses showed that they do not outperform the best known algorithms for some problems. Coja-Oghlan [Coj17] showed that BP-guided Decimation fails to find solutions for random $k$-SAT w.h.p. for density above $\rho_{0}2^{k}/k$ for a universal constant $\rho_{0}>0$, and thus does not outperform the best known algorithm from [Coj10]. Hetterich [Het16] also gave the same conclusion for SP-guided Decimation by showing that it fails w.h.p. for density above $(1+o_{k}(1))2^{k}\ln k/k$.

For random NAE-$k$-SAT, Gamarnik and Sudan [GS17b] showed that the balanced sequential local algorithms fail to find solutions for density above $(1+o_{k}(1))2^{k-1}\ln^{2}k/k$ for sufficiently large $k$. This means the algorithms do not outperform the best known algorithm, Unit Clause algorithm, which can find solutions w.h.p. for density up to $\rho\,2^{k-1}/k$ for some universal constant $\rho>0$ for sufficiently large $k$ [AKKT02]. The framework of balanced sequential local algorithms also covers BP-guided Decimation and SP-guided Decimation with the number of message passing iterations is bounded by $O((\ln\ln n)^{O(1)})$.

In our work, we obtain an analogous result. In Theorem 1, we show that w.h.p. strictly $2\mu(k,r)$-free sequential local algorithms fails to solve the random $k$-XORSAT problem when the clause density exceeds the clustering threshold. Then, in Theorem 3, we show that any sequential local algorithm with local rule that can compute the exact marginals are strictly $2\mu(k,r)$-free and thus fails to find a solution for random $k$-XORSAT problem. This theorem covers the sequential local algorithms with Belief Propagation BP and Survey Propagation SP as local rules.

The works from [AC08, ACR11] demonstrated the clustering phenomenon for several random CSPs, and conjectured that it could be an obstruction of solving those problems. [GS17a, GS17b] and subsequent works leveraged a different notion of clustering, named overlap gap property (OGP) by [GL18], to link the clustering phenomenon to the hardness rigorously. Gamarnik gave a detailed survey on it [Gam21].

This paper focuses on the vanilla version of the OGP. Given an instance $\Phi$ of the constraint satisfaction problem, we say it exhibits the overlap gap property with values $0\leq v_{1}<v_{2}$ if every two solutions $\sigma$ and $\sigma^{\prime}$ satisfy either $d(\sigma,\sigma^{\prime})\leq v_{1}$ or $d(\sigma,\sigma^{\prime})\geq v_{2}$, where $d$ is a metric on its solution space. (We assume $d$ is the Hamming distance throughout this paper.) Intuitively, it means every pair of solutions are either close to each other, or far from each other, and thus the solution space of the instance exhibits a topological discontinuity based on the proximity.

Now we illustrate how does the overlap gap property method. (Some details of the overlap gap property method is slightly different if we consider different variants of the OGP, but the overall idea of topological barrier stays the same.) Assume we have an algorithm $\mathcal{A}$ that takes a random instance $\mathbf{\Phi}$ as input and outputs an assignment $\sigma$ for the instance. The output $\sigma$ can be viewed as a random variable which depends on both the random instance $\mathbf{\Phi}$ and some internal random variables, represented by a random internal vector $\mathbf{I}$, of the algorithm. Let $\Phi$ and $I$ be realizations of $\mathbf{\Phi}$ and $\mathbf{I}$ respectively, and denote the output assignment as $\sigma_{0}=\sigma_{\Phi,I}$. We then re-randomize the components of the internal vector $I$ one-by-one. After each re-randomizing a component of $I$, we run the algorithm again to generate a new output assignment. Then, we obtain a sequence of assignments $\sigma_{0},\sigma_{1},\cdots,\sigma_{T}$ for the instance $\Phi$, where $T$ is the number of components of the random vector $I$ that we have re-randomized. Next, we show that the algorithm is insensitive to its input in the sense that when one of the components of the random internal vector $\mathbf{I}$ is re-randomized, the output assignment almost remains unchanged, In particular, $d(\sigma_{i},\sigma_{i+1})$ is smaller than $v_{2}-v_{1}$. We also show that the algorithm has certain freeness in the sense that when all components in the random internal are re-randomized the output assignment is expected to change a lot. In particular, $\mathop{{}\mathbb{E}}\left[{d(\sigma_{0},\sigma_{T})}\right]$ should be larger than $v_{2}$. These two properties together imply that the sequence of assignments cannot ”jump” over the overlap gap, while two ends of the sequence probably lie in different clusters. Therefore, there should be an assignment $\sigma_{T_{0}}$ that falls in the gap, namely, there exists $T_{0}>0$ such that $v_{1}\leq d(\sigma_{0},\sigma_{T_{0}})\leq v_{2}$. If the probability that the algorithm successfully finds a solution is greater than some small value $s_{n}$ slowly converging to 0, then there could be a very small probability that both $\sigma_{0}$ and $\sigma_{T_{0}}$ are solutions of the instance $\Phi$, with $v_{1}\leq d(\sigma_{0},\sigma_{T_{0}})\leq v_{2}$. Even though this probability is very small, it still has the chance to violates the OGP of the instance. Then, by contradiction, we could conclude that the probability that the algorithm succeeds in finding a solution is smaller than $s_{n}=o(1)$, namely, w.h.p. the algorithm fails in finding a solution.

Instead of considering the overlap gap property of the entire instance $\mathbf{\Phi}$, we move our focus to the overlap gap property of a sub-instance of $\mathbf{\Phi}$. Indeed, the sub-instance we consider is the 2-core instance $\mathbf{\Phi_{c}}$ induced by the 2-core of the factor graph representation of the random instance $\mathbf{\Phi}$. In [IKKM12, AM15], they proved that the 2-core instance $\mathbf{\Phi_{c}}$ exhibits the overlap gap property with $v^{\prime}_{1}=o(n)$ and $v^{\prime}_{2}=\epsilon_{k}n$ for some constant $\epsilon_{k}>0$ for clause density $r_{core}(k)<r<r_{sat}(k)$. We remove all variables not in the core instance from the sequence of assignments $\sigma_{0},\sigma_{1},\cdots,\sigma_{T}$ we obtained above, then it becomes a sequence of assignments $\sigma^{\prime}_{0},\sigma^{\prime}_{1},\cdots,\sigma^{\prime}_{T}$ for the core instance. We also prove that the algorithm is insensitive to its input with respect to the core instance in the sense that $d(\sigma^{\prime}_{i},\sigma^{\prime}_{i+1})<v^{\prime}_{2}-v^{\prime}_{1}$, and has certain freeness so that $\mathop{{}\mathbb{E}}\left[{d(\sigma^{\prime}_{0},\sigma^{\prime}_{T})}\right]>v^{\prime}_{2}$. By repeating the above argument of the overlap gap property method, we can conclude that w.h.p. the algorithm fails in find a solution.

Our proof can also be used for the non-sequential local algorithms. Since the local rule $\tau$ runs on the local neighborhood of each variable in parallel, the values assigned to variables do not depend on each other. Informally speaking, there is no long-range dependency among those assigned values. Therefore, re-randomizing one component of the internal vector $I$, say $I_{i+1}$, only affects the value $\sigma(x_{i+1})$ assigned to the corresponding variable $x_{i+1}$. So, we have $d(\sigma_{i},\sigma_{i+1})\leq 1<v^{\prime}_{2}-v^{\prime}_{1}$. Hence, we can obtain the same result as Theorem 1 for non-sequential local algorithms with the same proof.

The vanilla version of OGP helps us rule out some large classes of algorithms on random CSPs for relatively high clause densities, but it is not sophisticated enough to close the statistical-to-computational gap in some cases such as random NAE-$k$-SAT discussed in [GS17b] and random $k$-XORSAT discussed in this paper (more details in Section 2). There have been some recent works trying to improve the notion of OGP by developing different variants of OGP. The most notable one is multi-OGP [Wei22, BH22, HS22, GKPX23, GK23], which succeeds in closing the statistical-to-computational gap in certain models. However, it is not clear about the relation between the clustering property and the multi-OGP.

The random $k$-XORSAT instance $\mathbf{\Phi}$ is a random variable, and the $\tau$-decimation algorithm DEC_τ is a randomized algorithm. Therefore, the assignment output by the $\tau$-decimation algorithm DEC_τ on input $\mathbf{\Phi}$ is also a random variable. The outcomes of the output assignment depend on the random instance $\mathbf{\Phi}$, the order of variables being chosen, and the value selection based on the output from the local rule $\tau$. Now we introduce two random variables to explicitly represent the order of variables and the value selection so that we can have a more concrete language to discuss how the randomness from both the instance and the algorithm affects the output assignment. We adopt the notation from [GS17b] in the following discussion.

The order of variables can be represented by a random vector $\mathbf{Z}=(\mathbf{Z}_{1},\mathbf{Z}_{2},\cdots,\mathbf{Z}_{n})$ whose entries are $n$ i.i.d. random variables with uniform distribution over the interval $[0,1]\subset\mathbb{R}$, independent of the random instance $\mathbf{\Phi}$. We call $\mathbf{Z}$ the ordering vector of the algorithm. For all $i\in[n]$, the variable $x_{i}$ in the instance $\mathbf{\Phi}$ is associated with the random variable $\mathbf{Z}_{i}$. In each iteration of the algorithm, the unassigned variable $x_{i}$ with the largest value $\mathbf{Z}_{i}$, among all other unassigned variables, is selected. In the other words, we can construct the permutation $s:[n]\rightarrow[n]$ such that $\mathbf{Z}_{s(1)}>\mathbf{Z}_{s(2)}>\cdots>\mathbf{Z}_{s(n)}$, and for all $t\in[n]$ the variable $x_{s(t)}$ is selected in the $t$-th iteration. The value selection based the output from the local rule $\tau$ can be represented by a random vector $\mathbf{U}=(\mathbf{U}_{1},\mathbf{U}_{2},...,\mathbf{U}_{n})$ whose entries are $n$ i.i.d. random variables with uniform distribution over the interval $[0,1]\subset\mathbb{R}$. We call $\mathbf{U}$ the internal vector of the algorithm. In the $t$-th iteration of the algorithm, the value $\sigma(x_{s(t)})$ assigned to the selected variable $x_{s(t)}$ is set to be 1 if $\mathbf{U}_{t}<\tau(B_{\mathbf{\Phi}_{t}}(x_{s(t)},R))$, and 0 otherwise. Conditioning on $\mathbf{\Phi}$, $\mathbf{Z}$ and $\mathbf{U}$, the output assignment $\sigma$ can be uniquely determined. Therefore, we can view the $\tau$-decimation algorithm DEC_τ as a deterministic algorithm on random input $(\mathbf{\Phi},\mathbf{Z},\mathbf{U})$, and denote by $\sigma_{\mathbf{\Phi},\mathbf{Z},\mathbf{U}}$ the output of the algorithm.