# Faster algorithm for Unique $(k,2)$-CSP

Or Zamir
Institute for Advanced Study, Princeton, NJ USA

###### Abstract

In a $(k,2)$-Constraint Satisfaction Problem we are given a set of arbitrary
constraints on pairs of $k$-ary variables, and are asked to find an assignment
of values to these variables such that all constraints are satisfied. The
$(k,2)$-CSP problem generalizes problems like $k$-coloring and $k$-list-
coloring. In the Unique $(k,2)$-CSP problem, we add the assumption that the
input set of constraints has at most one satisfying assignment.

Beigel and Eppstein gave an algorithm for $(k,2)$-CSP running in time
$O\left(\left(0.4518k\right)^{n}\right)$ for $k>3$ and
$O\left(1.356^{n}\right)$ for $k=3$, where $n$ is the number of variables.
Feder and Motwani improved upon the Beigel-Eppstein algorithm for $k\geq 11$.
Hertli, Hurbain, Millius, Moser, Scheder and Szedlák improved these bounds for
Unique $(k,2)$-CSP for every $k\geq 5$.

We improve the result of Hertli et al. and obtain better bounds for Unique
$(k,2)$-CSP for $k\geq 5$. In particular, we improve the running time of
Unique $(5,2)$-CSP from $O\left(2.254^{n}\right)$ to $O\left(2.232^{n}\right)$
and Unique $(6,2)$-CSP from $O\left(2.652^{n}\right)$ to
$O\left(2.641^{n}\right)$.

Recently, Li and Scheder also published an improvement over the algorithm of
Hertli et al. in the same regime as ours. Their improvement does not include
quantitative bounds, we compare the works in the paper.

##  1 Introduction

The general Constraint Satisfaction Problem, in which we are asked to find an
assignment to a set of variables that satisfies a list of arbitrary
constraints, is NP-Complete. Furthermore, it is widely believed that a
substantial improvement over the naive exhaustive search is unlikely for the
general CSP problem and even for special cases of it like The _Boolean_
Satisfiability Problem (SAT). Nevertheless, when the structure of the input is
restricted in a certain manner, there are known improvements in the form of
_moderately exponential_ algorithms. These are algorithms that still have an
exponential running time, yet achieve an exponential improvement over the
exhaustive search bounds.

The study of moderately exponential algorithms for NP-Complete problems is
extensive. In fact, exponential yet better-than-naive algorithms for NP-
Complete problems were known for some problems, for example The Travelling
Salesman Problem, long before the definition of NP. A survey of Woeginger
[Woe03] covers and refers to dozens of papers exploring such algorithms for
many problems including satisfiability, graph coloring, knapsack, TSP, maximum
independent sets and more. Subsequent review article of Fomin and Kaski [FK13]
and book of Fomin and Kratsch [FK10] further cover the topic of exact
exponential-time algorithms.

Two of the most notable problems for which the study of moderately exponential
algorithms was fruitful are $k$-satisfiability (usually abbreviated as
$k$-SAT) and graph coloring.

For satisfiability, the running time of the trivial algorithm enumerating over
all possible assignments is $O^{*}(2^{n})$. No algorithms solving SAT in time
$O^{*}\left(\left(2-\varepsilon\right)^{n}\right)$ for any $\varepsilon>0$ are
known, and a popular conjecture called The _Strong_ Exponential Time
Hypothesis [CIP09] states that no such algorithm exists. On the other hand,
for every fixed $k$ there exists a constant $\varepsilon_{k}>0$ such that
$k$-SAT (i.e., SAT on formulas in CNF form with at most $k$ literals in every
clause) can be solved in
$O^{*}\left(\left(2-\varepsilon_{k}\right)^{n}\right)$ time. A result of this
type was first published by Monien and Speckenmeyer in 1985 [MS85]. A long
list of improvements for the values of $\varepsilon_{k}$ were published since,
including the celebrated 1998 PPSZ algorithm of Paturi, Pudlák, Saks and Zane
[PPSZ05] and the recent improvement over it by Hansen, Kaplan, Zamir and Zwick
[HKZZ19]. The PPSZ bound was originally obtained only for the case of input
formulas with a unique satisfying assignment, its analysis was extended to the
general case more than a decade later by Hertli [Her14].

For graph coloring, i.e, the problem of deciding whether a graph is
$k$-colorable, the naive exhaustive search algorithm takes $O(k^{n})$ time.
Nevertheless, it is known that computing the chromatic (or coloring) number of
a graph (i.e., the smallest $k$ for which the graph is $k$-colorable) can be
done in exponential time that does not depend on $k$. The first such result
was an $O^{*}(3^{n})$ algorithm of Lawler [Law76]. A long line of works
followed until finally an algorithm computing the chromatic number in
$O^{*}(2^{n})$ time was devised by Björklund, Husfeldt and Koivisto in 2009
[BHK09]. This is conjectured to be optimal. For $k\leq 6$ there are algorithms
solving $k$-colorability exponentially faster than $O(2^{n})$ [BE05][Zam20].
It is currently not known even if $7$-coloring can be solved exponentially
faster than the general $O(2^{n})$ bound of computing the coloring number. One
of the biggest open problems in this field is whether $k$-coloring can be
solved in $O^{*}\left(\left(2-\varepsilon_{k}\right)^{n}\right)$ time for
every fixed $k$.

Both examples are special cases of the more general Constraint Satisfaction
Problem. In an $(a,b)$-formula, we have $n$ variables such that each of them
can take a value in $[a]:=\\{1,\ldots,a\\}$ and a list of constraints such
that each constraint may depend on at most $b$ variables. Every such
constraint can be equivalently replaced by a disjunction of at most $a^{b}$
constraints of the form $\left(x_{1}\neq c_{1}\;\vee\;x_{2}\neq
c_{2}\;\vee\;\ldots\;\vee\;x_{b}\neq c_{b}\right)$ where $x_{1},\ldots,x_{b}$
are (not necessarily distinct) variables and $c_{1},\ldots,c_{b}\in[a]$ are
possible values. Thus, we can think of every $(a,b)$-formula as a list of
constraints of that form. In the $(a,b)$-CSP problem we are given a
$(a,b)$-formula and need to decide whether or not there is an assignment to
the variables that satisfies all constraints. In the Unique $(a,b)$-CSP
problem we add the assumption that if there is such an assignment it is
unique. Note that $k$-SAT is the same as $(2,k)$-CSP, and that $k$-coloring is
a special case of $(k,2)$-CSP. We later elaborate on the close relation
between the $(k,2)$-CSP and $k$-coloring problems.

In this paper we focus on obtaining better algorithms for Unique $(k,2)$-CSP.

###  1.1 Possible running time

Denote by $c_{a,b}$ the infimum of constants $c$ such that $(a,b)$-CSP on
formulas with $n$ variables can be solved in
$O\left(\left(c+o(1)\right)^{n}\right)$ time. Naively, $c_{a,b}\leq a$ as we
can simply try all $a^{n}$ possible assignments to the variables. A simple
improvement comes from the use of _down-sampling_. Given a $(a,b)$-formula we
may randomly restrict each variable to $a^{\prime}<a$ uniformly chosen values.
Each satisfying assignment is not ruled out by the restriction with
probability $\left(\frac{a^{\prime}}{a}\right)^{n}$. After this down-sampling
step, we are left with a $(a^{\prime},b)$-formula. Thus, for every
$a^{\prime}<a$ we have $c_{a,b}\leq\frac{a}{a^{\prime}}\cdot
c_{a^{\prime},b}$. In particular, $c_{a,b}\leq\frac{a}{2}c_{2,b}$. As we know
that $k$-SAT can be solved exponentially faster than $O(2^{n})$ for every
fixed $k$, we have that $c_{2,b}<2$ and in particular the strict inequality
$c_{a,b}<a$ holds for every $a,b$.

On the other hand, $(a,b)$-CSP is clearly NP-Complete for every $a>1$ except
of the special case of $(a,b)=(2,2)$ (which is the polynomial $2$-SAT). The
Exponential Time Hypothesis [CIP09] states that there exists some constant
$c>0$ such that $3$-SAT takes $\Omega(2^{cn})$ time to solve. Traxler [Tra08]
showed that assuming the Exponential Time Hypothesis, there exists some
$c^{\prime}>0$ such that $c_{k,2}>k^{c^{\prime}}$. Namely, even for $b=2$ the
$(k,2)$-CSP problem becomes strictly more complex as $k$ increases.

###  1.2 $(k,2)$-CSP and $k$-Coloring

Consider the following hierarchy of three problems:

  * •

$k$-Coloring: given a graph with $n$ vertices, determine whether it is
$k$-colorable.

  * •

$k$-List-Coloring: given a graph with $n$ vertices and a list of at most $k$
allowed colors (from a possibly larger universe of colors) for each vertex,
determine if there is a proper coloring of the graph such that each vertex is
colored with one of the allowed colors in its list.

  * •

$(k,2)$-CSP: given $n$ variables that can admit values from $[k]$ and a list
of arbitrary constraints involving one or two variables each, determine if
there is an assignment of values to the variables that satisfies all
constraints.

Each problem is a special case of the next one. Every instance of $k$-coloring
is also an instance of $k$-list-coloring where all lists are simply $[k]$.
Every instance of $k$-list-coloring is also an instance of $(k,2)$-CSP.
Nevertheless, while $k$-coloring and $k$-list-coloring can both be solved in
$O^{*}(2^{n})$ time regardless of $k$ [BHK09], Traxler’s reduction [Tra08]
shows that there is some constant $k_{0}$ such that for every $k>k_{0}$ we
have $c_{k,2}\geq 2$. Let $k_{0}$ be the minimal such constant. It is
currently known that $c_{4,2}<2$ and thus $k_{0}\geq 4$.

In [Zam20] it was recently shown that if $k$-list-coloring can be solved in
$O^{*}\left(\left(2-\varepsilon\right)^{n}\right)$ time for some
$\varepsilon>0$ then $\left(k+2\right)$-coloring can also be solved in
$O^{*}\left(\left(2-\varepsilon^{\prime}\right)^{n}\right)$ for some
$\varepsilon^{\prime}>0$. In particular, $\left(k_{0}+2\right)$-coloring can
be solved exponentially faster than $O(2^{n})$. As $k_{0}\geq 4$, this
resulted in the first $O^{*}\left(\left(2-\varepsilon\right)^{n}\right)$ time
algorithms for $5$-coloring and $6$-coloring. This gives a strong motivation
for improving upper bounds for $(k,2)$-CSP, with the goal of improving the
bound on $k_{0}$. In particular, showing that $(5,2)$-CSP can be solved in
$O^{*}\left(\left(2-\varepsilon\right)^{n}\right)$ time would result in the
first $O^{*}\left(\left(2-\varepsilon\right)^{n}\right)$ time algorithm for
$7$-coloring.

###  1.3 Previous results

By the down-sampling argument we can reduce $(k,2)$-CSP to the polynomial
$(2,2)$-CSP (i.e., $2$-SAT) and get an expected running time of
$O\left(\left(\frac{k}{2}\right)^{n}\right)$. Beigel and Eppstein [BE05] gave
an algorithm for $(k,2)$-CSP running in time
$O\left(\left(0.4518k\right)^{n}\right)$ for $k>3$ and
$O\left(1.356^{n}\right)$ for $k=3$. Feder and Motwani [FM02] give a
$(k,2)$-CSP algorithm based on the $k$-SAT PPZ algorithm, which is the
predecessor of the PPSZ one. They improve on the bound of Beigel and Eppstein
only for $k\geq 11$. Hertli, Hurbain, Millius, Moser, Scheder and Szedlák
[HHM+16] improved the bounds for Unique $(k,2)$-CSP for every $k\geq 5$.
Several other works [Sch99] [LLLX08] [Sch10] focus on the case where $b>2$.

###  1.4 Our contribution

k | Downsampling+2SAT | PPZ FM [FM02] | BE [BE05] | PPSZ [HHM+16] | Our algorithm
---|---|---|---|---|---
3 | 1.5 | 1.818 | _1.365_ | 1.434 | -
4 | 2 | 2.214 | _1.808_ | 1.849 | -
5 | 2.5 | 2.606 | 2.259 | _2.254_ | 2.232
6 | 3 | 2.994 | 2.711 | _2.652_ | 2.641
7 | 3.5 | 3.381 | 3.163 | _3.045_ | 3.042
Figure 1: Comparisons of the exponent base in Unique $(k,2)$-CSP algorithms

We present an algorithm that improves on the result of Hertli et al. and
obtain better bounds for Unique $(k,2)$-CSP for $k\geq 5$. In particular, we
improve the running time of Unique $(5,2)$-CSP from $O\left(2.254^{n}\right)$
to $O\left(2.232^{n}\right)$ and Unique $(6,2)$-CSP from
$O\left(2.652^{n}\right)$ to $O\left(2.641^{n}\right)$. Our result is compared
to the previous ones in Table 1.

We obtain our result by combining the strengths of both PPSZ and the Beigel-
Eppstein algorithms. Intuitively, we make the following insight regarding
PPSZ-type algorithms. Throughout the run of the PPSZ algorithm, it slowly
manipulates the CSP formula. For every $k^{\prime}<k$ there is some time-point
such that if we stop the algorithm at that point then the formula roughly
looks like a $(k^{\prime},2)$-CSP formula. Furthermore, the rest of the
algorithm run would have looked similar to running PPSZ on a
$(k^{\prime},2)$-formula. Thus, for $k\geq 5$ we may stop the run of the PPSZ
algorithm when the formula looks similar to a $(4,2)$-CSP or $(3,2)$-CSP
formula, and then switch to using the Beigel-Eppstein algorithm which is
faster than PPSZ for $k\leq 4$.

In Section 2 we give an extensive overview of the previous results we need to
use. Then in Section 3 we introduce our algorithm and obtain the improved
bounds. In Section 4 we sketch possible improvements to the analysis of
Section 3 and show that even with a completely ideal analysis of our algorithm
we would improve the bound for $k=5$ from $O(2.232^{n})$ only to
$O(2.223^{n})$. Thus, to prove that $k_{0}\geq 5$, if true, additional
algorithmic tools are necessary. In Section 5 we conclude our work, discuss
more possible uses for the PPSZ-related observations, and present open
problems.

###  1.5 Comparison with a recent work of Li and Scheder

Recently, Li and Scheder [LS21] also published an improvement for the PPSZ-
type algorithm of Hertli et al. for Unique CSP. Their algorithm does not use
the Beigel-Eppstein algorithm and just modifies the PPSZ-type algorithm itself
in a different manner to ours. They prove that this modification gives an
exponential improvement over the bounds of Hertli et al., but do not give a
quantitative bound of this improvement. We could not find a way to compute
such a bound from their paper, but suspect this improvement is very small.

Li and Scheder also observe that during the run of the PPSZ-type algorithm
when the number of color choices of a variable is very low (in their
algorithm, when it reaches $2$), then there are better ways to settle the
value of the variable than continuing the run of the PPSZ algorithm. In their
case, they do so by randomly picking one of the two colors for the variable.

Our work can be seen as a refinement of this idea in two different ways.
First, we cut off the PPSZ run with small color sets yet larger than two.
Second, we resolve the remaining instance with a variant of the Beigel-
Eppstein algorithm, which is much better than a random choice.

##  2 Relevant overview of previous work

In this section we give an overview of all previous results that are used in
our algorithm. We repeat and refine some of the theorems used in these papers
for their later use in Section 3.

###  2.1 The algorithm of Beigel and Eppstein

The algorithm of Beigel and Eppstein [BE05] solves a CSP by performing a
series of local reductions that either reduce the number of variables in the
CSP or the number of allowed values in some of the variables.

An example for such a local reduction that is of particular interest to us
follows.

######  Lemma 1.

[Lemma 2 of [BE05]] Let $(V,F)$ be a CSP in which each variable $x\in V$ has
$k(x)$ allowed values. Let $x$ be a variable with $k(x)=2$, then there exists
a set $F^{\prime}$ of additional constraints, each of size two, such that
$(V,F)$ is satisfiable if and only if $(V\setminus\\{x\\},F\cup F^{\prime})$
is satisfiable, with the same number of allowed values for each variable
$y\neq x$.

The result claimed in [BE05] is that their algorithm solves $(3,2)$-CSPs in
time $O\left(1.3645^{n}\right)$ and $(k,2)$-CSPs for $k>3$ in time
$O\left(\left(0.4518k\right)^{n}\right)$. Note that $1.3645>1.3554=0.4518\cdot
3$. In fact, the result proved in their paper is slightly stronger than that.
The following Theorem follows from [BE05].

######  Theorem 1.

[Section 5 of [BE05]] Let $(V,F)$ be a CSP with $|V|=n_{3}+n_{4}$ variables
such that $n_{3}$ variables have three allowed values and $n_{4}$ variables
have four allowed values, then we can solve it in time
$O\left(1.3645^{n_{3}}\cdot 1.8072^{n_{4}}\right)$.

The claimed results follow from Theorem 1 immediately. For $(3,2)$-CSPs we
simply have $n_{3}=n,\;n_{4}=0$ and for $(k,2)$-CSPs with $k>3$ we down-sample
each variable to $4$ out of its $k$ possible values and then use the theorem
with $n_{3}=0,\;n_{4}=n$, with a total expected run-time of
$O\left(\left(\frac{k}{4}\right)^{n}\cdot
1.8072^{n}\right)=O\left(\left(0.4518k\right)^{n}\right)$. Nevertheless, for
our use we need to fully use the power of Theorem 1 and we even slightly
refine it with the following statement, from now on referred to as _the
extended BE algorithm_.

######  Theorem 2.

Denote by

$BE(i):=\begin{cases}1&\quad\text{if }i\leq 2\\\ 1.3645&\quad\text{if }i=3\\\
0.4518\cdot i&\quad\text{if }i\geq 4\end{cases}.$

Let $(V,F)$ be a CSP in which each variable $x\in V$ has $k(x)$ allowed
values. Let $n_{i}$ be the number of variables $x$ in $V$ such that $k(x)=i$.
Then, we can solve $(V,F)$ in $O\left(\prod_{i}BE(i)^{n_{i}}\right)$ expected
time.

###### Proof.

The $n_{1}$ variables with a single possible value can be ignored. The $n_{2}$
variables with two possible values can be eliminated using Lemma 1. For every
$i>4$ we use down-sampling to reduce the number of allowed values to four. We
finally apply Theorem 1. ∎

###  2.2 The PPZ and PPSZ-type algorithms

In this section we present an overview of [FM02] and [HHM+16]. We state
theorems of both papers and their variants that are useful for our analysis,
and adapt some of their notation. Throughout the section we discuss only
instances with a unique satisfying assignment.

######  Definition 1 ($D$-implication).

Let $F$ be a $(k,2)$-CSP formula over a set $V$ of variables, $x\in V$ be a
variable, $c\in[k]$ be a possible value, $\alpha_{0}$ a partial assignment,
and $D\in\mathbb{N}$. We say that $\alpha_{0}$ $D$-implies $x\neq c$ and write
$\alpha_{0}\models_{D}\left(x\neq c\right)$ if there is a subset of
constraints $G\subseteq F$ of size $|G|\leq D$ such that $G\wedge\alpha_{0}$
implies $\left(x\neq c\right)$.

By enumeration, we can check whether $\alpha_{0}\models_{D}\left(x\neq
c\right)$ in $O\left(|F|^{D}\cdot poly(n)\right)$ time, which is polynomial in
$n,k$ if $D$ is a constant and sub-exponential in $n$ even if $D$ is a slow-
enough growing function of $n$. For the rest of the section we fix $D$.

######  Definition 2 (Eligible values).

Let $F$ be a $(k,2)$-CSP formula over a set $V$ of variables, $\alpha_{0}$ a
partial assignment, and $x\in V\setminus V(\alpha_{0})$ a variable which value
is not assigned in $\alpha_{0}$. We denote by

$\mathcal{A}\left(x,\alpha_{0}\right):=\\{c\in[k]\;|\;\alpha_{0}\not\models_{D}\left(x\neq
c\right)\\}$

the set of all possible values for $x$ that are not ruled out by
$D$-implication from $\alpha_{0}$.

We can now describe the PPSZ algorithm (adapted from SAT [PPSZ98] to CSP in
[HHM+16]). Given a $(k,2)$-CSP $F$, we begin with $\alpha_{0}=\emptyset$ the
empty assignment and incrementally add variables to it, hoping to finish with
a satisfying assignment. In particular, we choose a permutation $\pi$ of the
variables $V$ uniformly at random, and then choose an assignment for the
variables of $V$ one-by-one according to the order of $\pi$. When we reach a
variable $x$, we compute $\mathcal{A}\left(x,\alpha_{0}\right)$ in sub-
exponential time, pick a uniformly random $c\sim
U\left(\mathcal{A}\left(x,\alpha_{0}\right)\right)$, and extend $\alpha_{0}$
by setting $\alpha_{0}(x)=c$.

Pick a uniform random permutation $\pi$ of the set $V$ of variables;

Set $\alpha_{0}=\emptyset$;

for  _$x\in V$ in the order dictated by $\pi$_ do

Draw $c\sim U\left(\mathcal{A}\left(x,\alpha_{0}\right)\right)$ uniformly;

Set $\alpha_{0}(x):=c$;

Return $\alpha_{0}$;

Algorithm 1 The PPSZ algorithm

Algorithm 1 runs in sub-exponential time and returns some assignment
$\alpha_{0}$ to all variables of $V$. It is clear that the probability of
$\alpha_{0}$ to satisfy $F$, assuming that $F$ is satisfiable, is at least
$k^{-n}$. We next prove that for formulas $F$ with exactly one satisfying
assignment $\alpha$, the probability that Algorithm 1 produces the satisfying
assignment $\alpha_{0}=\alpha$ is in fact exponentially larger. For the rest
of the section we assume that $F$ has a unique satisfying assignment and
denote it by $\alpha$.

######  Definition 3 (Ultimately eligible values).

Let $F$ be a $(k,2)$-CSP formula uniquely satisfied by $\alpha$, $\pi$ be a
permutation of its variables $V$ and $x\in V$ some variable.
We let $V_{\pi,x}:=\\{y\in V\;|\;\pi(y)<\pi(x)\\}$ be the set of all variables
appearing before $x$ in $\pi$,
$\alpha_{\pi,x}:={\left.\kern-1.2pt\alpha\vphantom{\big{|}}\right|_{V_{\pi,x}}}$
be the partial assignment resulting by restricting $\alpha$ to $V_{\pi,x}$ and
then we denote by
$\mathcal{A}\left(x,\pi\right):=\mathcal{A}\left(x,\alpha_{\pi,x}\right)$ the
set of all possible values for $x$ that are not ruled out by $D$-implication
when we reach $x$ in a PPSZ iteration with permutation $\pi$, given that all
previous variables were set correctly.

We observe that Algorithm 1 returns $\alpha$ if and only if it draws the
correct value for _every_ variable. In particular, for a specific permutation
$\pi$ the probability of success is exactly $\prod_{x\in
V}\frac{1}{|\mathcal{A}\left(x,\pi\right)|}$. For a random permutation then,
the probability of success is

$\mathbb{E}_{\pi}\left[\prod_{x\in
V}\frac{1}{|\mathcal{A}\left(x,\pi\right)|}\right]\geq k^{-\sum_{x\in
V}\mathbb{E}_{\pi}\left[\log_{k}|\mathcal{A}\left(x,\pi\right)|\right]}$

where we use Jensen’s inequality. In particular, it is enough to give an upper
bound on
$\mathbb{E}_{\pi}\left[\log_{k}|\mathcal{A}\left(x,\pi\right)|\right]$ that
holds for every variable $x$.

###  2.3 The PPZ-type algorithm of Feder and Motwani

In the PPZ-type variant of Feder and Motwani [FM02], a simpler variant where
$D=1$ is presented and analysed. Namely, a possible value $c$ for a variable
$x$ is ruled out if and only if a variable $y$ appeared before $x$ in the
permutation and was assigned a value $c^{\prime}$ such that the constraint
$\left(x\neq c\;\vee\;y\neq c^{\prime}\right)$ appears in the list of
constraints. When we reach the variable $x$, we uniformly guess a value for it
out of all values that are not ruled out in that manner.

######  Lemma 2.

Let $(V,F)$ be the sets of variables and constraints in a Unique $(k,2)$-CSP.
Denote by $\varphi$ the unique satisfying assignment of $(V,F)$. For every
variable $x\in V$ and every value $\varphi(x)\neq c^{\prime}\in[k]$ other than
the value $x$ is assigned in $\varphi$, there exists a variable
$y=y_{x,c^{\prime}}\in V\setminus\\{x\\}$ such that $\left(x\neq
c^{\prime}\;\vee\;y\neq\varphi(y)\right)\in F$.

###### Proof.

Assume by contradiction that there exists a variable $x$ and a value
$c^{\prime}\neq\varphi(x)$ for which $\left(x\neq
c^{\prime}\;\vee\;y\neq\varphi(y)\right)\notin F$ for every variable $y$.
Consider the assignment $\varphi^{\prime}$ such that
$\varphi^{\prime}(x)=c^{\prime}$ and $\varphi^{\prime}(y)=\varphi(y)$ for
every $y\neq x$. It is a satisfying assignment as well, and
$\varphi^{\prime}\neq\varphi$ which contradicts the uniqueness assumption. ∎

Instead of uniformly drawing a permutation $\pi\sim S_{|V|}$ of the variables,
we (equivalently) independently draw a _time_ value $\pi(x)\sim
U\left(\left[0,1\right]\right)$ uniformly for every variable $x$, and let
$\pi$ be the permutation induced by the order of the time values $\pi(x)$ for
$x\in V$.

We observe that if $\pi(y_{x,c^{\prime}})<\pi(x)$ then
$c^{\prime}\notin\mathcal{A}\left(x,\pi\right)$. In particular, if
$\pi(x)=p\in[0,1]$ then for every $c^{\prime}\neq\varphi(x)$ with probability
at least $p$ we have that $c^{\prime}\notin\mathcal{A}\left(x,\pi\right)$.

######  Lemma 3.

For every variable $x$, we have

$\mathbb{E}_{\pi}\left[\log_{k}|\mathcal{A}\left(x,\pi\right)|\;\;\middle|\;\;\pi(x)=p\right]\leq\sum_{i=0}^{k-1}\binom{k-1}{i}\left(1-p\right)^{i}p^{k-1-i}\log_{k}\left(1+i\right).$

###### Proof.

For the analysis, we may assume that we rule out values only by the
constraints involving $x$ and one of the variables $y_{x,c^{\prime}}$ for
$c^{\prime}\neq\varphi(x)$. This holds since ruling out more variables can
only decrease the size of $\mathcal{A}\left(x,\pi\right)$.

If the variables $y_{x,c^{\prime}}$ are distinct for all
$c^{\prime}\neq\varphi(x)$, then the right hand side of the lemma’s statement
is exactly the expected size of $\mathcal{A}\left(x,\pi\right)$, conditioned
on $\pi(x)=p$. This is simply the expectation of $\log_{k}\left(1+i\right)$
where $i\sim Binomial\left(k-1,1-p\right)$ is a binomial random variable.

Generally, let $A_{c^{\prime}}$ be the indicator for the event that
$\pi(y_{x,c^{\prime}})>p$. We need to upper bound
$\mathbb{E}[\log_{k}\left(1+\sum_{c^{\prime}\neq\varphi(x)}A_{c^{\prime}}\right)]$.
Let $A^{\prime}_{c^{\prime}}$ be independent Bernoulli random variables with
probability $(1-p)$ to be $1$ and probability $p$ to be $0$. By concavity of
the function $\log_{k}(1+z)$ and Jensen’s inequality it follows that
$\mathbb{E}[\log_{k}\left(1+\sum_{c^{\prime}\neq\varphi(x)}A_{c^{\prime}}\right)]\leq\mathbb{E}[\log_{k}\left(1+\sum_{c^{\prime}\neq\varphi(x)}A^{\prime}_{c^{\prime}}\right)]$,
which concludes our proof. The complete proof of the last statement appears in
[HHM+16] as Lemma $A.1$. ∎

Denote by
$S^{\prime}_{k,2}:=\int_{0}^{1}\sum_{i=0}^{k-1}\binom{k-1}{i}\left(1-p\right)^{i}p^{k-1-i}\log_{k}\left(1+i\right)dp$.
By Lemma 3,
$\mathbb{E}\left[\log_{k}|\mathcal{A}\left(x,\pi\right)|\right]=\int_{0}^{1}\mathbb{E}_{\pi}\left[\log_{k}|\mathcal{A}\left(x,\pi\right)|\;\;\middle|\;\;\pi(x)=p\right]dp\leq
S^{\prime}_{k,2}$, this concludes the analysis of the Feder-Motwani PPZ-type
algorithm.

######  Theorem 3 ([FM02]).

The success probability of a PPZ iteration is at least
$k^{-S^{\prime}_{k,2}}$.

###  2.4 The PPSZ-type algorithm of Hertli et al.

In the PPSZ algorithm analysed in [HHM+16] more involved $D$-implications are
considered. In the analysis for $D=1$, we noticed that for every variable $x$
and every value $c^{\prime}\neq\varphi(x)$ there exists some variable
$y_{x,c^{\prime}}$ such that if $\pi(y_{x,c^{\prime}})<\pi(x)$ then
$c^{\prime}\notin\mathcal{A}\left(x,\pi\right)$.

We say that a variable $y$ is _decided_ with respect to some partial
assignment $\alpha_{0}$ if $|\mathcal{A}\left(y,\alpha_{0}\right)|=1$, i.e.,
if $\alpha_{0}$ already $D$-implies the correct value of $y$ in $\varphi$. The
main observation is that if in time $p:=\pi(x)$ the variable
$y_{x,c^{\prime}}$ is decided then
$c^{\prime}\notin\mathcal{A}\left(x,\pi\right)$. The variable
$y_{x,c^{\prime}}$ is necessarily decided if $\pi(y_{x,c^{\prime}})<p$ but can
also be decided if it is yet to appear in the permutation. Thus, the
probability of $y_{x,c^{\prime}}$ being decided at time $p$ is strictly larger
than $p$.

We give an intuitive reasoning for the probability of a variable being
decided. Denote by $q_{k}(p)$ the probability that a variable $x$ is decided
by time $p$. The variable $x$ is decided by time $p$ if $\pi(x)<p$ or
alternatively if for every $c^{\prime}\neq\varphi(x)$ the variable
$y_{x,c^{\prime}}$ is by itself decided at time $p$. In particular, $q_{k}(p)$
is a solution to the recurrence $q_{k}(p)=p+(1-p)q_{k}(p)^{k-1}$. We thus
denote by $q_{k}(p)$ the smallest non-negative real solution to that
recurrence, it can be analytically computed for every $k$ as it is simply a
root of a polynomial.

This intuitive argument is of course not complete and lacks many technical
details. Nevertheless, this statement does hold, and the following
strengthening of Lemma 3 and Theorem 3 are proven in [HHM+16].

######  Lemma 4.

[$A.1$ in [HHM+16]] For every variable $x$, we have

$\mathbb{E}_{\pi}\left[\log_{k}|\mathcal{A}\left(x,\pi\right)|\;\;\middle|\;\;\pi(x)=p\right]\leq\sum_{i=0}^{k-1}\binom{k-1}{i}\left(1-q_{k}\left(p\right)\right)^{i}q_{k}\left(p\right)^{k-1-i}\log_{k}\left(1+i\right).$

Denote by
$S_{k,2}:=\int_{0}^{1}\sum_{i=0}^{k-1}\binom{k-1}{i}\left(1-q_{k}\left(p\right)\right)^{i}q_{k}\left(p\right)^{k-1-i}\log_{k}\left(1+i\right)dp$.

######  Theorem 4 (Correctness of [HHM+16]).

Let $F$ be a Unique $(k,2)$-CSP formula, then for every variable $x$ it holds
that $\mathbb{E}_{\pi}\left[\log_{k}|\mathcal{A}\left(x,\pi\right)|\right]\leq
S_{k,2}+\varepsilon_{D}$, where $\varepsilon_{D}$ is some error parameter that
depends only on $D$ and goes to $0$ as $D$ goes to infinity.

##  3 Faster Unique $(k,2)$-CSP algorithm

On a very high-level, our algorithm combines Hertli et al.’s PPSZ (Section
2.2) with the BE algorithm (Section 2.1). We begin by illustrating our idea
intuitively (initially ignoring some crucial technical details to be discussed
later). Consider a run of the PPSZ algorithm, as described in Section 2.2. For
the early variables in the permutation $\pi$, it is very likely that
$|\mathcal{A}\left(x,\pi\right)|=k$, since $\alpha_{0}$ assigns values to very
few variables. On the other hand, for the last variables in the permutation,
it is very likely that $|\mathcal{A}\left(x,\pi\right)|=1$. It turns out that
in any point throughout the run of a PPSZ iteration, the sizes
$|\mathcal{A}\left(x,\alpha_{0}\right)|$ for the remaining variables $x\in
V\setminus V(\alpha_{0})$ are quite concentrated. Furthermore, after most of
the variables have $|\mathcal{A}\left(x,\alpha_{0}\right)|\approx
k^{\prime}<k$ the remaining portion of the PPSZ iteration strongly resembles a
PPSZ algorithm for $(k^{\prime},2)$-CSP formulas. As we see in Table 1, for
$k<5$ PPSZ behaves worse on $(k,2)$-CSP formulas than the BE algorithm.

Thus, in our algorithm, we begin with an iteration of PPSZ but halt it
somewhere in the middle of the permutation when the sizes
$|\mathcal{A}\left(x,\alpha_{0}\right)|$ are concentrated in $1,2,3,4$. At
that point, we use the extended BE algorithm shown in Section 2.1.

We set some parameter $t\in[0,1]$ to be chosen later and consider the
following algorithm.

Pick a uniform random permutation $\pi$ of the set $V$ of variables;

Denote by $\pi_{<t}$ the prefix of $\pi$ of size $t|V|$ and by $V_{<t}$ the
variables appearing in it;

Set $\varphi=\emptyset$;

for  _$x\in V_{ <t}$ in the order dictated by $\pi_{<t}$_ do

Draw $c\sim U\left(\mathcal{A}\left(x,\varphi\right)\right)$ uniformly;

Set $\varphi(x):=c$;

Run the extended BE algorithm on the remaining CSP $F$;

Return the solution $\varphi$;

Algorithm 2 Our algorithm

Consider an iteration of Algorithm 2. Denote by $R_{i}$ the number of
variables that appeared in $V_{<t}$ and had
$|\mathcal{A}\left(x,\pi\right)|=i$. Denote by $\varphi^{\prime}$ the partial
assignment constructed by time $t$. Let $B_{i}$ be the number of variables
that did not appear in $V_{<t}$ and had
$|\mathcal{A}\left(x,\varphi^{\prime}\right)|=i$.

######  Lemma 5.

The success probability of Algorithm 2 is
$\prod_{i=1}^{k}i^{-R_{i}}\cdot\prod_{i=5}^{k}\left(\frac{4}{i}\right)^{B_{i}}$.

###### Proof.

The probability of all PPSZ assignments to be correct is
$\prod_{i=1}^{k}i^{-R_{i}}$, as follows from Section 2.2. The probability of
the random down-sampling to not rule out the correct assignments is
$\prod_{i=5}^{k}\left(\frac{4}{i}\right)^{B_{i}}$. ∎

######  Lemma 6.

The running time of Algorithm 2 is $O\left(1.3645^{B_{3}}\cdot
1.8072^{B_{4}+\ldots+B_{k}}\right)$.

###### Proof.

The running time of the (partial) PPSZ iteration is polynomial. The running
time of the BE algorithm is $O(1.3645^{n_{3}}\cdot 1.8072^{n_{4}})$. ∎

Note that all $R_{i}$ and $B_{i}$ are fully determined by the choice of $\pi$.
Thus, for a specific choice of $\pi$, if we repeatedly run Algorithm 2 with
$\pi$ we expect finding a solution after
$\left(\prod_{i=1}^{k}i^{-R_{i}}\cdot\prod_{i=5}^{k}\left(\frac{4}{i}\right)^{B_{i}}\right)^{-1}$
iterations. In particular, after

$\left(\prod_{i=1}^{k}i^{-R_{i}}\cdot\prod_{i=5}^{k}\left(\frac{4}{i}\right)^{B_{i}}\right)^{-1}\cdot
O\left(1.3645^{B_{3}}\cdot
1.8072^{B_{4}+\ldots+B_{k}}\right)=\prod_{i=1}^{k}i^{R_{i}}\cdot\prod_{i}BE\left(i\right)^{B_{i}}$

computational steps. At this point, we would like to bound the expected
running time when picking a random $\pi$ with
$\prod_{i=1}^{k}i^{\mathbb{E}[R_{i}]}\cdot\prod_{i}BE\left(i\right)^{\mathbb{E}[B_{i}]}$.
Unfortunately, as we consider the running time and not a success probability
(as in the PPSZ algorithm), we need an inequality of the opposite direction to
Jensen’s inequality. Fortunately, this inequality _essentially still holds_ in
this case.

######  Lemma 7 (Wrong direction Jensen’s inequality is still kind-of right).

Let $\mathcal{A}$ be an algorithm with expected running time $2^{X}$
conditioned on the value of a random variable $X$. There exists an algorithm
$\mathcal{A^{\prime}}$ that successfully executes $\mathcal{A}$ with
probability at least $0.99$ and has an expected running time of
$O\left(2^{\mathbb{E}\left[X\right]}\cdot\mathbb{E}\left[X\right]\right)$.

###### Proof.

We apply Markov’s inequality twice. First, to observe that

$\Pr\left(X>\mathbb{E}[X]+1\right)\leq\frac{1}{1+\frac{1}{\mathbb{E}[X]}}=1-\frac{1}{\mathbb{E}[X]+1}.$

Hence, if we run $\mathcal{A}$ independently for
$6\left(\mathbb{E}\left[X\right]+1\right)$ times, then with probability at
least $1-e^{-6}>1-\frac{1}{200}$ at least one of these runs has
$X\leq\mathbb{E}\left[X\right]+1$. Second, conditioned on any value of $X$,
with probability at least $1-\frac{1}{200}$ algorithm $\mathcal{A}$ finishes
in less than $200\cdot 2^{X}$ computational steps. Thus, by union bound, if we
run algorithm $\mathcal{A}$ for $6\left(\mathbb{E}\left[X\right]+1\right)$
times, and terminate each run after $400\cdot 2^{\mathbb{E}[X]}$ computational
steps, then at least one run of $\mathcal{A}$ finishes with probability at
least $0.99$. ∎

######  Corollary 1.

We find a satisfying assignment with probability greater than $0.99$ in time

$O^{\star}\left(\prod_{i=1}^{k}i^{\mathbb{E}[R_{i}]}\cdot\prod_{i}BE\left(i\right)^{\mathbb{E}[B_{i}]}\right).$

We give a simpler analysis leading to slightly sub-optimal bounds. In Section
4 we sketch the possible improvements to the analysis presented here, and also
present a clear limit to the improvements that can be achieved by this
algorithm.

We slightly abuse notation by equating the numbers $R_{i},B_{i}$ with the sets
of variables they are counting. Let $x$ be a variable. For the analysis we can
assume that the algorithm rules out values for $x$ only due to the constraints
involving $x$ and some $y_{x,c^{\prime}}$. This holds as ruling out more
values can only improve the success probability of each iteration.

We first consider the case in which the variables $y_{x,c^{\prime}}$ for every
$c^{\prime}\neq\varphi(x)$ are all distinct.

######  Lemma 8.

For each variable $x$, we have

$\mathbb{E}\left[\sum_{i=1}^{k}Pr\left(x\in
R_{i}\right)\cdot\log_{k}i\right]\leq\int_{0}^{t}\sum_{i=0}^{k-1}\binom{k-1}{i}\left(1-q_{k}\left(p\right)\right)^{i}q_{k}\left(p\right)^{k-1-i}\log_{k}\left(1+i\right)dp.$

###### Proof.

This follows immediately from Lemma 4. ∎

######  Lemma 9.

Let $x$ be a variable for which $y_{x,c^{\prime}}$ are distinct for all
$c^{\prime}\neq\varphi(x)$. Then,

$\mathbb{E}\left[\sum_{i=3}^{k}Pr\left(x\in
B_{i}\right)\cdot\log_{k}EB\left(i\right)\right]\leq(1-t)\cdot\sum_{i=3}^{k}\binom{k-1}{i}\left(1-t\right)^{i}t^{k-1-i}\cdot\log_{k}EB\left(i\right).$

###### Proof.

For simplicity, we analyse this part with a PPZ-type analysis (rather than
PPSZ-type one), this is further discussed in Section 4. The probability that
$x\notin V_{<t}$ is $(1-t)$, and the probability that exactly $i$ out of the
$(k-1)$ variables $y_{x,c^{\prime}}$ do not appear in $V_{<t}$ is
$\binom{k-1}{i}\left(1-t\right)^{i}t^{k-1-i}$. ∎

Denote by

$\displaystyle\text{cost}(k,t):=$
$\displaystyle\int_{0}^{t}\sum_{i=0}^{k-1}\binom{k-1}{i}\left(1-q_{k}\left(p\right)\right)^{i}q_{k}\left(p\right)^{k-1-i}\log_{k}\left(1+i\right)dp$
$\displaystyle+(1-t)\cdot\sum_{i=3}^{k}\binom{k-1}{i}\left(1-t\right)^{i}t^{k-1-i}\cdot\log_{k}EB\left(i\right).$

If all variables had completely distinct $y_{x,c^{\prime}}$’s, then by Lemma 8
and Lemma 9 we would have that $(\star)$ and in particular the running time of
our algorithm is bounded by $O\left(k^{\text{cost}(k,t)n}\right)$ for any
choice of $t$. This would give us $O(2.22936^{n})$ for $k=5,t=0.23$ and
$O(2.64001^{n})$ for $k=6,t=0.35$. We now deal with the case in which these
are not distinct.

In the proof of Lemma 3 we faced the same problem and solved it by a simple
application of Jensen’s inequality to the concave function $\log_{k}(1+i)$.
Unfortunately, the function $\log_{k}EB\left(i\right)$ is not concave (for
$i=1,\ldots,k$) due to its values on $i=1,2$. Indeed, the left-hand side of
the inequality in Lemma 9 is higher than the right-hand side if these
variables are not distinct. On the other hand, when these variables are not
distinct then the term of Lemma 8 is much smaller.

Consider the expression

$\mathbb{E}\left[\sum_{i=1}^{k}Pr\left(x\in
R_{i}\right)\cdot\log_{k}i+\sum_{i=3}^{k}Pr\left(x\in
B_{i}\right)\cdot\log_{k}EB\left(i\right)\right]$

again. This time, we will assume that the variables $y_{x,c^{\prime}}$ are not
all distinct. Denote by
$k^{\prime}:=|\\{y_{x,c^{\prime}}\;\;|\;\;c^{\prime}\neq\varphi(x)\\}|<k-1$
the number of such distinct variables, and by $j_{1},\ldots,j_{k^{\prime}}$
their cardinalities (note that $\sum_{i=1}^{k^{\prime}}j_{i}=k-1$). Consider
the following expression.

$\displaystyle\mathbb{E}\Big{[}$
$\displaystyle\int_{0}^{t}\sum_{b_{1},\ldots,b_{k^{\prime}}\in\\{0,1\\}}q_{k}\left(p\right)^{k^{\prime}-\sum_{i=1}^{k^{\prime}}b_{i}}\cdot\left(1-q_{k}\left(p\right)\right)^{\sum_{i=1}^{k^{\prime}}b_{i}}\cdot\log_{k}\left(1+\sum_{i=1}^{k^{\prime}}j_{i}b_{i}\right)dp$
($\star\star\star$)
$\displaystyle+(1-t)\cdot\sum_{b_{1},\ldots,b_{k^{\prime}}\in\\{0,1\\}}t^{k^{\prime}-\sum_{i=1}^{k^{\prime}}b_{i}}\cdot(1-t)^{\sum_{i=1}^{k^{\prime}}b_{i}}\cdot\log_{k}EB\left(1+\sum_{i=1}^{k^{\prime}}j_{i}b_{i}\right)\Big{]}.$

Expression $(\star\star\star)$ is a generalized form of $\text{cost}(k,t)$ and
thus upper bounds $(\star\star)$ by the same arguments. Completely analysing
the behaviour of Expression $(\star\star\star)$ for different partitions is
rather technically involved and thus we simply enumerate over the few possible
cases (for small values of $k$). In Section 4 we further discuss the possible
improvements to the analysis of this section.

######  Theorem 5.

We solve Unique $(6,2)$-CSP in $O\left(2.641^{n}\right)$ time.

###### Proof.

For the choice $t=0.37$ we have that $\text{cost}(6,0.35)=\log_{6}(2.64001)$,
this choice of $t$ minimizes $\text{cost}(6,t)$. We verify that for $t=0.35$
Expression $(\star\star\star)$ is always lower than $\text{cost}(6,0.35)$ and
thus finish, as this implies that for every variable Expression $(\star\star)$
is bounded by $\text{cost}(6,0.35)$.

  * •

For the partition $(j_{1},j_{2},j_{3},j_{4})=(2,1,1,1)$ the value of
$(\star\star\star)$ in $t=0.35$ is $\log_{6}(2.62023)$.

  * •

For the partition $(j_{1},j_{2},j_{3})=(2,2,1)$ the value of
$(\star\star\star)$ in $t=0.35$ is $\log_{6}(2.61171)$.

  * •

For the partition $(j_{1},j_{2},j_{3})=(3,1,1)$ the value of
$(\star\star\star)$ in $t=0.35$ is $\log_{6}(2.58391)$.

  * •

For the partition $(j_{1},j_{2})=(3,2)$ the value of $(\star\star\star)$ in
$t=0.35$ is $\log_{6}(2.60366)$.

  * •

For the partition $(j_{1},j_{2})=(4,1)$ the value of $(\star\star\star)$ in
$t=0.35$ is $\log_{6}(2.54819)$.

  * •

For the partition $(j_{1})=(5)$ the value of $(\star\star\star)$ in $t=0.35$
is $\log_{6}(2.55566)$.

∎

######  Theorem 6.

We solve Unique $(5,2)$-CSP in $O\left(2.232^{n}\right)$ time.

###### Proof.

For the choice $t=0.23$ we have that $\text{cost}(5,0.23)=\log_{5}(2.22936)$,
this choice of $t$ minimizes $\text{cost}(5,t)$. This time, unfortunately, for
$t=0.23$ Expression $(\star\star\star)$ is not always lower than
$\text{cost}(5,0.23)$. In particular, it is for every partition except of
$(j_{1})=4$.

  * •

For the partition $(j_{1},j_{2},j_{3})=(2,1,1)$ the value of
$(\star\star\star)$ in $t=0.23$ is $\log_{5}(2.21658)$.

  * •

For the partition $(j_{1},j_{2})=(2,2)$ the value of $(\star\star\star)$ in
$t=0.23$ is $\log_{5}(2.21983)$.

  * •

For the partition $(j_{1},j_{2})=(3,1)$ the value of $(\star\star\star)$ in
$t=0.23$ is $\log_{5}(2.20499)$.

  * •

For the partition $(j_{1})=(4)$ the value of $(\star\star\star)$ in $t=0.23$
is $\log_{5}(2.24925)$.

Denote by $\alpha$ the fraction of variables for which the $y_{x,c^{\prime}}$
variables are all the same (i.e., variables with the only problematic
partition). With the choice $t=0.23$ the running time of our algorithm on a
formula is $O\left(\left(2.22936^{\left(1-\alpha\right)}\cdot
2.24925^{\alpha}\right)^{n}\right)$. On the other hand, if $\alpha$ is large
we can simply run the regular PPSZ algorithm and gain much. We see that by
setting $t=1$ and computing Expression $(\star\star\star)$ for the same
partition $(j_{1})=(4)$, gives a value of $\log_{5}(2.01077)$. Thus, running
regular PPSZ would give us a running time of
$O\left(\left(2.25303^{\left(1-\alpha\right)}\cdot
2.01077^{\alpha}\right)^{n}\right)$. We can therefore try both options
($t=0.23$ or $t=1$) simultaneously and thus get the running time of the faster
one. Both expressions balance at $\alpha=0.08612$, giving us a running time of
$O\left(2.23107^{n}\right)$. ∎

Computation identical to this of Theorem 5 gives running time of
$O\left(3.042^{n}\right)$ for $k=7$ with $t=0.44$.

##  4 Improvements and Limitations

In this section we sketch a possible improvement to the analysis of Section 3.
The purpose of this section is not to tighten the upper bound but to explain
the limitations of our algorithm and to convince that even with a tight
analysis of Algorithm 2 it will achieve running times that are only slightly
better than these we get in Section 3. In particular, if getting
$O\left(\left(2-\varepsilon\right)^{n}\right)$ time for $(5,2)$-CSP is
possible, new algorithmic tools are likely required.

Consider the expression
$\prod_{i=1}^{k}i^{\mathbb{E}[R_{i}]}\cdot\prod_{i}EB(i)^{\mathbb{E}[B_{i}]}$
$(\star)$ proven in Section 3 to upper bound the running time of our
algorithm. In Lemma 8 we give a likely tight bound for the term involving
$\mathbb{E}[R_{i}]$, yet in Lemma 9 we settle for a PPZ-type bound for
$\mathbb{E}[B_{i}]$ in which we consider only the events in which the
variables $y_{x,c^{\prime}}$ themselves appear before time $t$ and not the
events in which they are decided by that time. The reason for this discrepancy
becomes clear in the rest of the analysis. Due to the non-concave objective
function in $i$, we can no longer assume independence between the events of
each $y_{x,c^{\prime}}$ being decided. Nevertheless, later in Theorem 5 and
Theorem 6 we observe that while the term involving $\mathbb{E}[B_{i}]$ indeed
gets worse with dependencies, the other term involving $\mathbb{E}[B_{i}]$
gets significantly better with them and thus can cover for those dependencies.
Ideally, then, the simple PPZ-type bound of $t$ in Lemma 9 can be replaced
with the PPSZ-type bound of $q_{k}(t)$ in the total bound. This would result
in the following tighter cost function.

$\displaystyle\tilde{\text{cost}}(k,t):=$
$\displaystyle\int_{0}^{t}\sum_{i=0}^{k-1}\binom{k-1}{i}\left(1-q_{k}\left(p\right)\right)^{i}q_{k}\left(p\right)^{k-1-i}\log_{k}\left(1+i\right)dp$
$\displaystyle+(1-t)\cdot\sum_{i=3}^{k}\binom{k-1}{i}\left(1-q_{k}\left(t\right)\right)^{i}q_{k}\left(t\right)^{k-1-i}\cdot\log_{k}EB\left(i\right).$

With this ideal cost function, we would get running times of
$O\left(2.223^{n}\right)$ for Unique $(5,2)$-CSP (for $t=0.32$) and
$O\left(2.628^{n}\right)$ for Unique $(6,2)$-CSP (for $t=0.46$).

##  5 Conclusions and Open Problems

In Section 3 we presented an algorithm for Unique $(k,2)$-CSP with a running
time of $O(2.232^{n})$ for $k=5$. In Section 4 we argued that even with an
ideal analysis, the bound we get for $k=5$ is only the slightly better
$O(2.223^{n})$. Thus, it remains open and would likely require new algorithmic
tools to show that $(5,2)$-CSP can be solved in
$O\left(\left(2-\varepsilon\right)^{n}\right)$ time, or alternatively to rule
out the existence of such algorithm by reductions to popular conjectures. More
generally, we raise the following open problem.

######  Open Problem.

What is the maximal $k$ such that $(k,2)$-CSP can be solved in
$O\left(\left(2-\varepsilon\right)^{n}\right)$ time?

The main algorithmic observation in this paper is in fact a general insight
regarding the behaviour of PPSZ-type algorithms. The Beigel-Eppstein algorithm
[BE05] only works for $(k,2)$-CSP. On the other hand, the PPSZ-type algorithm
[HHM+16] generalizes to $b>2$ and is in fact currently the fastest algorithm
for Unique $(a,b)$-CSP with $b>2$ and any $a$. Using the tools we introduced
in this paper, it should be possible to turn any faster algorithm for
$(a,b)$-CSP for a specific $(a,b)$ into a faster $(a^{\prime},b)$-CSP
algorithm for all $a^{\prime}>a$.

Another follow-up question is whether our algorithm can be generalized to the
non-unique $(k,2)$-CSP case.

## References

  * [BE05] Richard Beigel and David Eppstein.  3-coloring in time $O(1.3289^{n})$.  Journal of Algorithms, 54(2):168–204, 2005.
  * [BHK09] Andreas Björklund, Thore Husfeldt, and Mikko Koivisto.  Set partitioning via inclusion-exclusion.  SIAM Journal on Computing, 39(2):546–563, 2009.
  * [CIP09] Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi.  The complexity of satisfiability of small depth circuits.  In International Workshop on Parameterized and Exact Computation, pages 75–85. Springer, 2009.
  * [FK10] F.V. Fomin and D. Kratsch.  Exact Exponential Algorithms.  Texts in Theoretical Computer Science. An EATCS Series. Springer Berlin Heidelberg, 2010.
  * [FK13] Fedor V Fomin and Petteri Kaski.  Exact exponential algorithms.  Communications of the ACM, 56(3):80–88, 2013.
  * [FM02] Tomás Feder and Rajeev Motwani.  Worst-case time bounds for coloring and satisfiability problems.  Journal of Algorithms, 45(2):192–201, 2002.
  * [Her14] Timon Hertli.  3-SAT faster and simpler - unique-SAT bounds for PPSZ hold in general.  SIAM J. Comput., 43(2):718–729, 2014.  Announced at FOCS’11.
  * [HHM+16] Timon Hertli, Isabelle Hurbain, Sebastian Millius, Robin A Moser, Dominik Scheder, and May Szedlák.  The ppsz algorithm for constraint satisfaction problems on more than two colors.  In International Conference on Principles and Practice of Constraint Programming, pages 421–437. Springer, 2016.
  * [HKZZ19] Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick.  Faster $k$-SAT algorithms using biased-PPSZ.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 578–589, 2019.
  * [Law76] Eugene L Lawler.  A note on the complexity of the chromatic number problem.  1976\.
  * [LLLX08] Liang Li, Xin Li, Tian Liu, and Ke Xu.  From k-sat to k-csp: Two generalized algorithms.  arXiv preprint arXiv:0801.3147, 2008.
  * [LS21] Shibo Li and Dominik Scheder.  Impatient ppsz–a faster algorithm for csp.  arXiv preprint arXiv:2109.02795, 2021.
  * [MS85] Burkhard Monien and Ewald Speckenmeyer.  Solving satisfiability in less than 2n steps.  Discrete Applied Mathematics, 10(3):287–295, 1985.
  * [PPSZ98] Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane.  An improved exponential-time algorithm for $k$-SAT.  In 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, pages 628–637, 1998.
  * [PPSZ05] Ramamohan Paturi, Pavel Pudlák, Michael E Saks, and Francis Zane.  An improved exponential-time algorithm for k-SAT.  Journal of the ACM (JACM), 52(3):337–364, 2005.
  * [Sch99] T Schoning.  A probabilistic algorithm for k-SAT and constraint satisfaction problems.  In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 410–414. IEEE, 1999.
  * [Sch10] Dominik Scheder.  Ppz for more than two truth values-an algorithm for constraint satisfaction problems.  arXiv preprint arXiv:1010.5717, 2010.
  * [Tra08] Patrick Traxler.  The time complexity of constraint satisfaction.  In International Workshop on Parameterized and Exact Computation, pages 190–201. Springer, 2008.
  * [Woe03] Gerhard J Woeginger.  Exact algorithms for NP-hard problems: A survey.  In Combinatorial optimization—eureka, you shrink!, pages 185–207. Springer, 2003.
  * [Zam20] Or Zamir.  Breaking the $2^{n}$ barrier for $5$-coloring and $6$-coloring.  2020\.