Tight lower bounds for the complexity of multicoloring∗
Marthe Bonamy†

Łukasz Kowalik‡

Michał Pilipczuk‡

Arkadiusz Socała‡

arXiv:1607.03432v3 [cs.DS] 16 Feb 2017

Marcin Wrochna‡

Abstract
In the multicoloring problem, also known as (a:b)-coloring or b-fold coloring, we are given a
graph G and a set of a colors, and the task is to assign a subset of b colors to each vertex of G
so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic
coloring problem (the b = 1 case) is equivalent to finding a homomorphism to the Kneser graph
KGa,b , and gives relaxations approaching the fractional chromatic number.
We study the complexity of determining whether a graph has an (a:b)-coloring. Our main
result is that this problem does not admit an algorithm with running time f (b)·2o(log b)·n , for any
computable f (b), unless the Exponential Time Hypothesis (ETH) fails. A (b + 1)n · poly(n)-time
algorithm due to Nederlof [2008] shows that this is tight. A direct corollary of our result is that
the graph homomorphism problem does not admit a 2O(n+h) algorithm unless ETH fails, even
if the target graph is required to be a Kneser graph. This refines the understanding given by
the recent lower bound of Cygan et al. [SODA 2016].
The crucial ingredient in our hardness reduction is the usage of detecting matrices of Lindström [Canad. Math. Bull., 1965], which is a combinatorial tool that, to the best of our
knowledge, has not yet been used for proving complexity lower bounds. As a side result, we
prove that the running time of the algorithms of Abasi et al. [MFCS 2014] and of Gabizon et
al. [ESA 2015] for the r-monomial detection problem are optimal under ETH.

∗

Work supported by the National Science Centre of Poland, grants number 2013/11/D/ST6/03073 (MP, MW) and
2015/17/N/ST6/01224 (AS). The work of Ł. Kowalik is a part of the project TOTAL that has received funding from
the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 677651). Michał Pilipczuk is supported by the Foundation for Polish Science (FNP) via the
START stipend programme.
†
CNRS, LaBRI, France
‡
University of Warsaw, Poland

1

Introduction

The complexity of determining the chromatic number of a graph is undoubtedly among the most
intensively studied computational problems. Countless variants, extensions, and generalizations
of graph colorings have been introduced and investigated. Here, we focus on multicolorings, also
known as (a:b)-colorings. In this setting, we are given a graph G, a palette of a colors, and a number
b ≤ a. An (a:b)-coloring of G is any assignment of b distinct colors to each vertex so that adjacent
vertices receive disjoint subsets of colors. The (a:b)-coloring problem asks whether G admits an
(a:b)-coloring. Note that for b = 1 we obtain the classic graph coloring problem. The smallest a for
which an (a:b)-coloring exists, is called the b-fold chromatic number, denoted by χb (G).
The motivation behind (a:b)-colorings can be perhaps best explained by showing the connection
with the fractional chromatic number. The fractional chromatic number of a graph G, denoted
χf (G), is the optimum value of the natural LP relaxation of the problem of computing the chromatic
number of G, expressed as ﬁnding a cover of the vertex set using the minimum possible number of
independent sets. It can be easily seen that by relaxing the standard coloring problem by allowing
b times more colors while requiring that every vertex receives b colors and adjacent vertices receive
disjoint subsets, with increasing b we approximate the fractional chromatic number better and
better. Consequently, limb→∞ χb (G)/b = χf (G).
23
14

23

35

51
24

12
13
25

34

25

45
13

34

45

51
23
14

51

14
24

24

25
34

35

13

45

35
12

12

Figure 1: A (5:2)-coloring of the dodecahedron (left) which can be seen as a homomorphism to
KG5,2 (the Petersen graph, right). The homomorphism is given by identifying the pairs of opposite
vertices in the corresponding regular solid.
Another interesting connection concerns Kneser graphs. Recall that for positive integers a, b
with b < a/2, the Kneser graph KGa,b has all b-element subsets of {1, 2, . . . , a} as vertices, and
two subsets are considered adjacent if and only if they are disjoint. For instance, KG5,2 is the
well-known Petersen graph (see Fig. 1, right). Thus, (a:b)-coloring of a graph G can be interpreted
as a homomorphism from G to the Kneser graph KGa,b (see Fig. 1). Kneser graphs are well studied
in the context of graph colorings mostly due to the celebrated result of Lovász [29], who determined
their chromatic number, initiating the ﬁeld of topological combinatorics.
Multicolorings and (a:b)-colorings have been studied both from combinatorial [7, 12, 27] and
algorithmic [5, 19, 20, 25, 26, 30, 31, 34] points of view. The main real-life motivation comes from
1

the problem of assigning frequencies to nodes in a cellular network so that adjacent nodes receive
disjoint sets of frequencies on which they can operate. This makes (near-)planar and distributed
settings particularly interesting for practical applications. We refer to the survey of Halldórsson
and Kortsarz [18] for a broader discussion.
In this paper we focus on the paradigm of exact exponential time algorithms: given a graph G on
n vertices and numbers a ≥ b, we would like to determine whether G is (a:b)-colorable as quickly as
possible. Since the problem is already NP-hard for a = 3 and b = 1, we do not expect it to be solvable
in polynomial time, and hence look for an eﬃcient exponential-time algorithm. A straightforward
dynamic programming approach yields an algorithm with running time1 O⋆ (2n · (b + 1)n ) as follows.
For each function η : V (G) → {0, 1, . . . , b} and each k = 0, 1, . . . , a, we create one boolean entry
D[η, k] denoting whether one can choose k independent sets in G so that every vertex v ∈ V (G) is
covered exactly η(v) times. Then value D[η, k] can be computed as a disjunction of values D[η ′ , k−1]
over η ′ obtained from η by subtracting 1 on vertices from some independent set in G.
This simple algorithm can be improved by ﬁnding an appropriate algebraic formula for the
number of (a:b)-colorings of the graph and using the inclusion-exclusion principle to compute it
quickly, similarly as in the case of standard colorings [2]. Such an algebraic formula was given by
Nederlof [33, Theorem 3.5] in the context of a more general Multi Set Cover problem. Nederlof
also observed that in the case of (a:b)-coloring, a simple application of the inclusion-exclusion
principle to compute the formula yields an O⋆ ((b + 1)n )-time exponential-space algorithm. Hua et
al. [22] noted that the formulation of Nederlof [33] for Multi Set Cover can be also used to obtain
a polynomial-space algorithm for this problem. By taking all maximal independent sets to be the
family in the Multi Set Cover problem, and applying the classic Moon-Moser upper bound on
their number [32], we obtain an algorithm for (a:b)-coloring that runs in time O⋆ (3n/3 · (b + 1)n )
and uses polynomial space. Note that by plugging b = 1 to the results above, we obtain algorithms
for the standard coloring problem with running time O⋆ (2n ) and exponential space usage, and with
running time O⋆ (2.8845n ) and polynomial space usage, which almost matches the fastest known
procedures [2].
The complexity of (a:b)-coloring becomes particularly interesting in the context of the Graph
Homomorphism problem: given graphs G and H, with n and h vertices respectively, determine
whether G admits a homomorphism to H. By the celebrated result of Hell and Nešetřil [21] the
problem is in P if H is bipartite and NP-complete otherwise. For quite a while it was open whether
there is an algorithm for Graph Homomorphism running in time 2O(n+h) . It was recently answered
in the negative by Cygan et al. [9]; more precisely, they proved that an algorithm with running
time 2o(n log h) would contradict the Exponential Time Hypothesis (ETH) of Impagliazzo et al. [23].
However, Graph Homomorphism is a very general problem, hence researchers try to uncover a
more ﬁne-grained picture and identify families of graphs H such that the problem can be solved more
eﬃciently whenever H ∈ H. For example, Fomin, Heggernes and Kratsch [13] showed that when
H is of treewidth at most t, then Graph Homomorphism can be solved in time O⋆ ((t + 3)n ). It
was later extended to graphs of cliquewidth bounded by t, with an O⋆ ((2t + 1)max{n,h} ) time bound
by Wahlström [36]. On the other hand, H needs not be sparse to admit eﬃcient homomorphism
testing: the family of cliques admits the O⋆ (2n ) running time as shown by Björklund et al. [2].
As noted above, this generalizes to Kneser graphs KGa,b , by the O⋆ ((b + 1)n )-time algorithm of
Nederlof. In this context, the natural question is whether the appearance of b in the base of the
exponent is necessary, or is there an algorithm running in time O⋆ (cn ) for some universal constant
c independent of b.
1

The O⋆ (·) notation hides factors polynomial in the input size.

2

Our contribution. We show that the algorithms for (a:b)-coloring mentioned above are essentially optimal under the Exponential Time Hypothesis. Speciﬁcally, we prove the following results:
Theorem 1. If there is an algorithm for (a:b)-coloring that runs in time f (b) · 2o(log b)·n , for
some computable function f (b), then ETH fails. This holds even if the algorithm is only required to
work on instances where a = Θ(b2 log b).
Corollary 2. If there is an algorithm for Graph Homomorphism that runs in time f (h) ·
2o(log log h)·n , for some computable function f (h), then ETH fails. This holds even if the algorithm
is only required to work on instances where H is a Kneser graph KGa,b with a = Θ(b2 log b).
The bound for (a:b)-coloring is tight, as the straightforward O⋆ (2n · (b + 1)n ) = 2O(log b)·n
dynamic programming algorithm already shows. At ﬁrst glance, one might have suspected that
(a:b)-coloring, as an interpolation between classical coloring and fractional coloring, both solvable
in 2O(n) time [17], should be just as easy; Theorem 1 refutes this suspicion.
Corollary 2 in particular excludes any algorithm for testing homomorphisms into Kneser graphs
with running time 2O(n+h) . It cannot give a tight lower bound matching
the result of Cygan

et al. [9] for general homomorphisms, because h = |V (KGa,b )| = ab is not polynomial in b. On
the other hand, it exhibits the ﬁrst explicit family of graphs H for which the complexity of Graph
Homomorphism increases with h.
In our proof, we ﬁrst show a lower bound for the list variant of the problem, where every vertex
is given a list of colors that can be assigned to it (see Section 2 for formal deﬁnitions). The list
version is reduced to the standard version by introducing a large Kneser graph KGa+b,b ; we need a
and b to be really small so that the size of this Kneser graph does not dwarf the size of the rest of
the construction. However, this is not necessary for the list version, where we obtain lower bounds
for a much wider range of functions b(n).
Theorem 3. If there is an algorithm for List (a:b)-coloring that runs in time 2o(log b)·n , then ETH
fails. This holds even if the algorithm is only required to work on instances where a = Θ(b2 log b)
and b = Θ(b(n)) for an arbitrarily chosen polynomial-time computable function b(n) such that
b(n) ∈ ω(1) and b(n) = O(n/ log n).
The crucial ingredient in the proof of Theorem 3 is the usage of d-detecting matrices introduced
by Lindström [28]. We choose to work with their combinatorial formulation, hence we shall talk
about d-detecting families. Suppose we are given some universe U and there is an unknown function
f : U → {0, 1, . . . , d − 1}, for some ﬁxed positive integer d. One may think of U as consisting of
coins of unknown weights that are integers between 0 and d − 1. We would like to learn f (the
weight ofPevery coin) by asking a small number of queries of the following form: for a subset X ⊆ U ,
what is e∈X f (e) (the total weight of coins in X)? A set of queries suﬃcient for determining all
the values of an arbitrary f is called a d-detecting family. Of course f can be learned by asking |U |
questions about single coins, but it turns out that signiﬁcantly fewer questions are needed: there
is a d-detecting family of size O(|U |/ log |U |), for every ﬁxed d [28]. The logarithmic factor in the
denominator will be crucial for deriving our lower bound.
Let us now sketch how d-detecting families are used in the proof of Theorem 3. Given an instance
ϕ of 3-SAT with n variables and O(n) clauses, and a number b ≤ n/ log n, we will construct an
instance G of List (a:b)-coloring for some a. This instance will have a positive answer if and
only if ϕ is satisﬁable, and the constructed graph G will have O(n/ log b) vertices. It can be easily
seen that this will yield the promised lower bound.
Partition the clause set C of ϕ into groups C1 , C2 , . . . , Cp , each of size roughly b; thus p = O(n/b).
Similarly, partition the variable set V of ϕ into groups V1 , . . . , Vq , each of size roughly log2 b; thus
3

q = O(n/ log b). In the output instance we create one vertex per each variable group—hence we
have O(n/ log b) such vertices—and one block of vertices per each clause group, whose size will
be determined in a moment. Our construction ensures that the set of colors assigned to a vertex
created for a variable group misses one color from some subset of b colors. The choice of the missing
color corresponds to one of 2log2 b = b possible boolean assignments to the variables of the group.
Take any vertex u from a block of vertices created for some clause group Cj . We make it adjacent
to vertices constructed for precisely those variable groups Vi , for which there is some variable in Vi
that occurs in some clause of Cj . This way, u can only take a subset of the above missing colors
corresponding to the chosen assignment on variables relevant to Cj . By carefully selecting the list
of u, and some additional technical gadgeteering, we can express a constraint of the following form:
the total number of satisﬁed literals in some subset of clauses of Cj is exactly some number. Thus,
we could verify that every clause of Cj is satisﬁed by creating a block of |Cj | vertices, each checking
one clause. However, the whole graph output by the reduction would then have O(n) vertices, and
we would not obtain any non-trivial lower bound. Instead, we create one vertex per each question
in a d-detecting family on the universe U = Cj , which has size O(|Cj |/ log |Cj |) = O(|Cj |/ log b).
Then, the total number of vertices in the constructed graph will be O(n/ log b), as intended.
Finally, we observe that from our main result one can infer a lower bound for the complexity
of the (r, k)-Monomial Testing problem. Recall that in this problem we are given an arithmetic
circuit that evaluates a homogenous polynomial P (x1 , x2 , . . . , xn ) over some ﬁeld F; here, a polynomial is homogenous if all its monomials have the same total degree k. The task is to verify whether
P has some monomial in which every variable has individual degree not larger than r, for a given palog r
rameter r. Abasi et al. [1] gave a randomized algorithm solving this problem in time O⋆ (2O(k· r ) ),
where k is the degree of the polynomial, assuming that F = GF(p) for a prime p ≤ 2r 2 + 2r. This
algorithm was later derandomized by Gabizon et al. [14] within the same running time, but under
the assumption that the circuit is non-cancelling: it has only input, addition, and multiplication
gates. Abasi et al. [1] and Gabizon et al. [14] gave a number of applications of low-degree monomial
detection to concrete problems. For instance, r-Simple k-Path, the problem of ﬁnding a walk of
log r
length k that visits every vertex at most r times, can be solved in time O⋆ (2O(k· r ) ). However,
for r-Simple k-Path, as well as other problems that can be tackled using this technique, the best
k
known lower bounds under ETH exclude only algorithms with running time O⋆ (2o( r ) ). Whether
the log r factor in the exponent is necessary was left open by Abasi et al. and Gabizon et al.
We observe that the List (a:b)-coloring problem can be reduced to (r, k)-Monomial Testlog r
ing over the ﬁeld GF(2) in such a way that an O⋆ (2k·o( r ) )-time algorithm for the latter would
imply a 2o(log b)·n -time algorithm for the former, which would contradict ETH. Thus, we show that
the known algorithms for (r, k)-Monomial Testing most probably cannot be sped up in general;
nevertheless, the question of lower bounds for speciﬁc applications remains open. However, going
through List (a:b)-coloring to establish a lower bound for (r, k)-Monomial Testing is actually
quite a detour, because the latter problem has a much larger expressive power. Therefore, we also
give a more straightforward reduction that starts from a convenient form of Subset Sum; this
reduction also proves the lower bound for a wider range of r, expressed as a function of k.
Outline. In Section 2 we set up the notation as well as recall deﬁnitions and well-known facts. We
also discuss d-detecting families, the main combinatorial tool used in our reduction. In Section 3
we prove the lower bound for the list version of the problem, i.e., Theorem 3. In Section 4 we give
a reduction from the list version to the standard version, thereby proving Theorem 1. Section 5 is
devoted to deriving lower bounds for low-degree monomial testing.
4

2

Preliminaries

Notation. We use standard graph notation, see e.g. [10, 11]. All graphs we consider in this paper
are simple and undirected. For an integer k, we denote [k] = {0, . . . , k − 1}. By ⊎ we denote the
disjoint union, i.e., by A ⊎ B we mean A ∪ B with the indication that A and B are disjoint. If I and
J are instances of decision problems P and R, respectively, then we say that I and J are equivalent
if either both I and J are YES-instances of respective problems, or both are NO-instances.
Exponential-Time Hypothesis. The Exponential Time Hypothesis (ETH) of Impagliazzo et
al. [23] states that there exists a constant c > 0, such that there is no algorithm solving 3-SAT in
time O⋆ (2cn ). During the recent years, ETH became the central conjecture used for proving tight
bounds on the complexity of various problems. One of the most important results connected to ETH
is the Sparsification Lemma [24], which essentially gives a reduction from an arbitrary instance of kSAT to an instance where the number of clauses is linear in the number of variables. The following
well-known corollary can be derived by combining ETH with the Sparsiﬁcation Lemma.
Theorem 4 (see e.g. Theorem 14.4 in [10]). Unless ETH fails, there is no algorithm for 3-SAT
that runs in time 2o(n+m) , where n, m denote the numbers of variables and clauses, respectively.
We need the following regularization result of Tovey [35]. Following Tovey, by (3,4)-SAT we call
the variant of 3-SAT where each clause of the input formula contains exactly 3 diﬀerent variables,
and each variable occurs in at most 4 clauses.
Lemma 5 ([35]). Given a 3-SAT formula ϕ with n variables and m clauses one can transform it
in polynomial time into an equivalent (3,4)-SAT instance ϕ′ with O(n + m) variables and clauses.
Corollary 6. Unless ETH fails, there is no algorithm for (3,4)-SAT that runs in time 2o(n) , where
n denotes the number of variables of the input formula.
List and nonuniform list (a:b)-coloring For integers a, b and a graph G with a function
L : V (G) → 2[a] (assigning a list of colors to every vertex), an L-(a:b)-coloring of G is an assignment
of exactly b colors from L(v) to each vertex v ∈ V (G), such that adjacent vertices get disjoint color
sets. The List (a:b)-coloring problem asks, given (G, L), whether an L-(a:b)-coloring of G exists.
As an intermediary step of our reduction, we will use the following generalization of list colorings
where the number of demanded colors varies with every vertex. For integers a, b, a graph G with
a function L : V (G) → 2[a] and a demand function β : V (G) → {1, . . . , b}, an L-(a:β)-coloring of
G is an assignment of exactly β(v) colors from L(v) to each vertex v ∈ V (G), such that adjacent
vertices get disjoint color sets. Nonuniform List (a:b)-coloring is then the problem in which
given (G, L, β) we ask if an L-(a:β)-coloring of G exists.
d-detecting families. In our reductions the following notion plays a crucial role.
Definition 7. A d-detecting family for a finite set U is a family F ⊆ 2U of subsets of U such that
for every two P
functions f, g : U → {0, . . . , d − 1}, f 6= g, there is a set S in the family such that
P
x∈S f (x) 6=
x∈S g(x).

A deterministic construction of sublinear, d-detecting families was given by Lindström [28],
together with a proof that even the constant factor 2 in the family size cannot be improved.

Theorem 8 ([28]). For every constant d ∈ N and finite set U , there is a d-detecting family F on
|
U of size log2|U|U
| · (1 + o(1)). Furthermore, F can be constructed in time polynomial in |U |.
d

5

Other constructions, generalizations, and discussion of similarPresults can be found in Grebinski
and Kucherov [16], and in Bshouty [3]. Note that the expression x∈S f (x) is just the product of f
as a vector in [d]|U | with the characteristic vector of S. Hence, instead of subset families, Lindström
speaks of detecting vectors, while later works see them as detecting matrices, that is, (0, 1)-matrices
with these vectors as rows (which deﬁne an injection on [d]|U | despite having few rows). Similar
deﬁnitions appear in the study of query complexity, e.g., as in the popular Mastermind game [6].
While known polynomial deterministic constructions of detecting families involve some number
theory or fourier analysis, their existence can be argued with an elementary probabilistic argument.
Intuitively,Pa random subset
P S ⊆ U will distinguish two distinct functions f, g : U → {0, . . . , d − 1}
(meaning x∈S f (x) 6= x∈S g(x)) with probability at least 21 . This is because any x where f and g
disagree is taken or not taken into S with probability 12 , while sums over S cannot agree in both cases
simultaneously, as they diﬀer by f (x) and g(x) respectively. There are dn · dn function pairs to be
distinguished. In any subset of pairs, at least half are distinguished by a random set in expectation,
thus at least one such set exists. Repeatedly ﬁnding such a set for undistinguished pairs, we get
| log 1 (dn · dn )| = O(n log d) sets that distinguish all functions. More strongly though, when two
2
functions diﬀer on more values, the probability of distinguishing them increases signiﬁcantly. Hence
we need fewer random sets to distinguish all pairs of distant functions. On the other hand, there
are few function pairs that are close, so we need few random sets to distinguish them all as well.
This allows to show that in fact O( logn n ) random sets are enough to form a d-detecting family with
d
positive probability [16].

Hardness of List (a:b)-coloring

3

In this section we show our main technical contribution: an ETH-based lower bound for List (a:b)coloring. The key part is reducing an n-variable instance 3-SAT to an instance of Nonuniform
List (a:b)-coloring with only O( logn b ) vertices. Next, it is rather easy to reduce Nonuniform
List (a:b)-coloring to List (a:b)-coloring. We proceed with the ﬁrst, key part.

3.1

The nonuniform case

We prove the following theorem through the remaining part of this section.
Theorem 9. For any instance φ of (3,4)-SAT with n variables and any integer 2 ≤ b ≤ n/ log2 n,
there is an equivalent instance (G, β, L) of Nonuniform List (a:2b)-coloring such that a =
O(b2 log b), |V (G)| = O( logn b ) and G is 3-colorable. Moreover, the instance (G, β, L) and the 3coloring of G can be constructed in poly(n) time.
Consider an instance φ of 3-SAT where each variable appears in at most four clauses. Let V
be the set of its variables and C be the set of its clauses. Note that 31 |V | ≤ |C| ≤ 43 |V |. Let
a = 12b2 · ⌊log2 b⌋. We shall construct, for some integers nV = O(|V |/ log b) and nC = O(|C|/b):
• a partition V = V1 ⊎ . . . ⊎ VnV of variables into groups of size at most ⌊log2 b⌋,
• a partition C = C1 ⊎ . . . ⊎ CnC of clauses into groups of size at most b,
• a function σ : {1, . . . , nV } → [12 · b · ⌊log2 b⌋],
such that the following condition holds:
For any j = 1, . . . , nC , the variables occurring in clauses of Cj are all diﬀerent and
they all belong to pairwise diﬀerent variable groups. Moreover, the indices of these
groups are mapped to pairwise diﬀerent values by σ.
6

(z)

In other words, any two literals of clauses in Cj have diﬀerent variables, and if they belong to Vi
and Vi′ respectively, then σ(i) 6= σ(i′ ).
Lemma 10. Partitions V = V1 ⊎ . . . ⊎ VnV , C = C1 ⊎ . . . ⊎ CnC and a function σ satisfying (z)
can be found in time O(n).
Proof. We ﬁrst group variables, in a way such that the following holds: (P1) the variables occurring
in any clause are diﬀerent and belong to diﬀerent variable groups. To this end, consider the graph
G1 with variables as vertices and edges between any two variables that occur in a common clause
(i.e. the primal graph of φ). Since no clause contains repeated variables, G1 has no loops. Since
every variable of φ occurs in at most four clauses, and since those clauses contain at most two
other variables, the maximum degrees of G1 is at most 8. Hence G1 can be greedily colored with 9
colors. Then, we reﬁne the partition given by colors to make every group have size at most ⌊log2 b⌋,
producing in total at most nV := ⌈|V |/⌊log 2 b⌋⌉ + 9 groups V1 , . . . , VnV . (P1) holds, because any
two variables occurring in a common clause are adjacent in G1 , and thus get diﬀerent colors, and
thus are assigned to diﬀerent groups.
Next, we group clauses in a way such that: (P2) the variables occurring in clauses of a group Cj
are all diﬀerent and belong to diﬀerent variable groups. For this, consider the graph G2 with clauses
as vertices, and with an edge between clauses if they contain two diﬀerent variables from the same
variable group. By (P1), G2 has no loops. Since every clause contains exactly 3 variables, each
variable is in a group with at most ⌊log2 b⌋ − 1 others, and every such variable occurs in at most 4
clauses, the maximum degree of G2 is at most 12(⌊log 2 b⌋ − 1). We can therefore color G2 greedily
with 12⌊log 2 b⌋ colors. Similarly as before, we partition clauses into nC := ⌈|C|/b⌉ + 12⌊log 2 b⌋
monochromatic groups C1 , . . . , CnC of size at most b each. Then (P2) holds by construction of the
coloring.
Finally, consider a graph G3 with variable groups as vertices, and with an edge between two
variable groups if they contain two diﬀerent variables occurring in clauses from a common clause
group. More precisely, Vi and Vi′ are adjacent if there are two diﬀerent variables x ∈ Vi and x′ ∈ Vi′ ,
and a clause group Cj with clauses c and c′ (possibly c = c′ ), such that x occurs in c and x′ occurs
in c′ . By (P2), G3 has no loops. Since a variable has at most ⌊log2 b⌋ − 1 other variables in its
group, each of these variables occur in at most 4 clauses, each of these clauses has at most b − 1
other clauses in its group, and each of these contains exactly 3 variables, the maximum degree of
G3 is at most 4 · (⌊log2 b⌋ − 1) · (b − 1) · 3. We can therefore color it greedily into 12b⌊log2 b⌋ colors.
Let σ be the resulting coloring. By (P2) and the construction of this coloring, (z) holds.
The colorings can be found in linear time using standard techniques. Note that we have nV =
⌈|V |/⌊log2 b⌋⌉ + 9 = O(|V |/ log b). Moreover, since b ≤ n/ log2 n, we get log2 b ≤ log2 n ≤ nb =
Θ(|C|/b) and hence nC = ⌈|C|/b⌉ + 12⌊log 2 b⌋ = O(|C|/b).

7

V1

⌊log2 b⌋ variables
V2

...
C1

b clauses

V3

...

...

v1

VnV

u1,1 u1,2

...

v2

...

v3

...

vn V

u1,2nF unC ,1 unC ,2 unC ,2nF

...

...

Cn C
w1

wnC

Figure 2: (left) The groups of variables and clauses of the formula; literals in C1 are joined with
their variables. Since no variable of V2 occurs in C1 , we have 2 6∈ I1 – this may allow us to make
σ(2) the same number as σ(3), say, reducing the total number a of colors needed. (right) The
constructed graph; thick lines represent edges to all vertices corresponding to C1 .
For every 1 ≤ i ≤ nV , the set Vi of variables admits 2|Vi | ≤ b diﬀerent assignments. We will
therefore say that each assignment on Vi is given by an integer x ∈ [b], for example by interpreting
the ﬁrst |Vi | bits of the binary representation of x as truth values for variables in Vi . Note that
when |Vi | < log2 b, diﬀerent integers from [b] may give the same assignment on Vi .
For 1 ≤ j ≤ nC , let Ij ⊆ {1, . . . , nV } be the set of indices of variable groups that contain
some variable occurring in the clauses of Cj . Since every clause contains exactly three literals,
property (z) means that |Ij | = 3|Cj | and that σ is injective over each Ij . See Fig. 2.
For 1 ≤ j ≤ nC , let {Cj,1 , . . . , Cj,nF } be a 4-detecting family of subsets of Cj , for some nF =
O( logb b ) (we can assume nF does not depend on j by adding arbitrary sets when |Cj | < b). For
every 1 ≤ k ≤ nF , let Cj,nF +k = Cj \ Cj,k .
We are now ready to build the graph G, the demand function β : V (G) → {1, . . . , 2b}, and the
list assignment L as follows.
(1) For 1 ≤ i ≤ nV , create a vertex vi with β(vi ) = b − 1 and L(vi ) = {b · σ(i) + x | x ∈ [b]}.
(2) For 1 ≤ j ≤ nC and 1 ≤ k ≤ 2nF , create a vertex uj,k adjacent to each vi for i ∈ Ij .
Let β(uj,k ) = |Cj,k | and
L(uj,k ) = {b·σ(i) + x | 1 ≤ i ≤ nV , x ∈ [2|Vi | ] such that
x gives an assignment of Vi that satisﬁes some clause of Cj,k }.
(3) For 1 ≤ j ≤ nC , create a vertex wSj , adjacent to each vi for i ∈ Ij and to each uj,k (1 ≤ k ≤ 2nF ).
Let β(wj ) = 2|Cj | and L(wj ) = i∈Ij {b · σ(i) + x | x ∈ [b]}.

Before giving a detailed proof of the correctness, let us describe the reduction in intuitive terms.
Note that vertices of type vi get all but one color from their list; this missing color, say b · σ(i) + xi ,
for some xi ∈ [b], deﬁnes an assignment on Vi . For every j = 1, . . . , nC the goal of the gadget
consisting of wj and vertices uj,k is to express the constraint that every clause in Cj has a literal
satisﬁed by this assignment. Since wj , uj,k are adjacent to all vertices in {vi | i ∈ Ij }, they may
only use the missing colors (of the form b · σ(i) + xi , where i ∈ Ij ). Since |Ij | = 3|Cj |, there are
3|Cj | such colors and 2|Cj | of them go to wj . This leaves exactly |Cj | colors for vertices of type uj,k ,
corresponding to a choice of |Cj | satisﬁed literals from the 3|Cj | literals in clauses of Cj . The lists
and demands for vertices uj,k guarantee that exactly |Cj,k | chosen satisﬁed literals occur in clauses
of Cj,k . The properties of 4-detecting families will ensure that every clause has exactly one chosen,
satisﬁed literal, and hence at least one satisﬁed literal. We proceed with formal proofs.
8

Lemma 11. If φ is satisfiable then G is L-(a:β)-colorable.
Proof. Consider a satisfying assignment η for φ. For 1 ≤ i ≤ nV , let xi ∈ [2|Vi | ] be an integer giving
the same assignment on Vi as η. For every clause c of φ, choose one literal satisﬁed byη in it,
[a]
and let ic be index of the group Vic containing the literal’s variable. Let α : V (G) → ≤2b
be the
L-(a:β)-coloring of G deﬁned as follows, for 1 ≤ i ≤ nV , 1 ≤ j ≤ nC , 1 ≤ k ≤ 2nF :
• α(vi ) = L(vi ) \ {b · σ(i) + xi }
• α(uj,k ) = {b · σ(ic ) + xic | c ∈ Cj,k }
• α(wj ) = {b · σ(i) + xi | i ∈ Ij \ {ic | c ∈ Cj }}.
Let us ﬁrst check that every vertex v gets colors from its list L(v) only. This is immediate for
vertices vi and wj , while for uj,k it follows from the fact that xic gives a partial assignment to Vi
that satisﬁes some clause of Cj,k .
Now let us check that for every vertex v, the coloring α assigns exactly β(v) colors to v. For
α(vi ) this follows from the fact that |L(vi )| = b and 0 ≤ xi < 2|Vi | ≤ b. Since by property (z), σ is
injective on Ij , and thus on {ic | c ∈ Cj,k } ⊆ Ij , we have |α(uj,k )| = |Cj,k | = b(uj,k ). Similarly, since
σ is injective on Ij and |Ij \ {ic | c ∈ Cj }| = 3|Cj | − |Cj | = 2|Cj |, we get |α(wj )| = 2|Cj | = β(wj ).
It remains to argue that the sets assigned to any two adjacent vertices are disjoint. There are
three types of edges in the graph, namely vi uj,k , vi wj , and wj uj,k . The disjointness of α(wj ) and
α(uj,k ) is immediate from the deﬁnition of α, since Cj,k ⊆ Cj . Fix j = 1, . . . , nC . Since σ is injective
on Ij , for any two diﬀerent i, i′ ∈ Ij , we have b · σ(i) + xi 6∈ L(vi′ ). Hence,
[
α(vi ) = {b · σ(i) + x | i ∈ Ij and x ∈ [b]} \ {b · σ(i) + xi | i ∈ Ij }.
i∈Ij

Since α(uj,k ), α(wj ) ⊆ {b · σ(i) + xi | i ∈ Ij }, it follows that edges of types vi uj,k and vi wj received
disjoint sets of colors on their endpoints, concluding the proof.
Lemma 12. If G is L-(a:β)-colorable then φ is satisfiable.
Proof. Assume that G is L-(a:β)-colorable, and let α be the corresponding coloring.
For 1 ≤ i ≤ nV , we have |L(vi )| = b and |α(vi )| = b − 1, so vi misses exactly one color from its
list. Let b · σ(i) + xi , for some xi ∈ [b], be the missing color. We want to argue that the assignment
x for φ given by xi on each Vi satisﬁes φ.
Consider any clause group Cj , for 1 ≤ j ≤ nC . Every vertex in {wj } ∪ {uj,k | 1 ≤ k ≤ 2nF }
contains
{vi | i ∈ Ij } in its neighborhood. Therefore, the sets α(uj,k ) and α(wj ) are disjoint from
S
′
′
α(v
i ). Since L(uj,k ), L(wj ) ⊆ {b · σ(i) + x | i ∈ Ij , x ∈ [b]}, we get that α(uj,k ) and α(wj )
i∈Ij
are contained in the set of missing colors {b · σ(i) + xi | i ∈ Ij } (corresponding to the chosen
assignment). By property (z), this set has exactly |Ij | = 3|Cj | diﬀerent colors. Of these, exactly
2|Cj | are contained in α(wj ). Let the remaining |Cj | colors be {b · σ(i) + xi | i ∈ Jj }, for some
subset Jj ⊆ Ij of |Cj | indices.
Since α(uj,k ) is disjoint from α(wj ), we have α(uj,k ) ⊆ {b · σ(i) + xi | i ∈ Jj } for all k. By
deﬁnition of Ij , for every i ∈ Jj ⊆ Ij there is a variable in Vi that appears in some clause of Cj . By
property (z), it can only occur in one such clause, so let li be the literal in the clause of Cj where
it appears. For every color b · σ(i) + xi ∈ α(uj,k ), by deﬁnition of the lists for uj,k we know that xi
gives a partial assignment to Vi that satisﬁes some clause of Cj,k . This means xi makes the literal
li true and li occurs in a clause of Cj,k . Therefore, for each k, at least |α(uj,k )| = |Cj,k | literals from
the set {li | i ∈ Jj } occur in clauses of Cj,k and are made true by the assignment x.
9

Let f : Cj → {0, 1, 2, 3} be the function
assigning to each clause c ∈ Cj the number of literals
P
of c in {li | i ∈ Jj }. By the above, c∈Cj,k f (c) ≥ |Cj,k | for 1 ≤ k ≤ 2nF . Since each literal in
P
{li | i ∈ Jj } belongs to some clause of Cj , we have c∈Cj f (c) = |Jj | = |Cj |. Then,
X

f (c) =

c∈Cj,k

X

f (c) −

c∈Cj

X

f (c) ≤ |Cj | − |Cj,nF +k | = |Cj,k |.

c∈Cj,nF +k

P
Hence c∈Cj,k f (c) = |Cj,k | for 1 ≤ k ≤ 2nF . Let g : Cj → {0, 1, 2, 3} be the constant function
g ≡ 1. Note that
X
X
g(c) = |Cj,k | =
f (c).
c∈Cj,k

c∈Cj,k

Since {Cj,1 , . . . , Cj,nF } is a 4-detecting family, this implies that f ≡ 1. Thus, for every clause c of
Cj we have f (c) = 1, meaning that there is a literal from the set {li | i ∈ Jj } in this clause. All
these literals are made positive by the assignment η, therefore all clauses of Cj are satisﬁed. Since
j = 1, . . . , nC was arbitrary, this concludes the proof that η is a satisfying assignment for φ.
The construction can clearly be made in polynomial time and the total number of vertices is
nV + nC · O( logb b ) + nC = O( logn b ). Moreover, we get a proper 3-coloring of G, by coloring vertices
of the type vi by color 1, vertices of the type uj,k by color 2, and vertices of the type wj by color 3.
By Lemmas 11 and 12, this concludes the proof of Theorem 9.

3.2

The uniform case

In this section we reduce the nonuniform case to the uniform one, and state the resulting lower
bound on the complexity of List (a:b)-coloring.
Lemma 13. For any instance I = (G, β, L) of Nonuniform List (a:b)-coloring where the graph
G is t-colorable, there is an equivalent instance (G, L′ ) of List ((a + tb):b)-coloring. Moreover,
given a t-coloring of G the instance (G, L′ ) can be constructed in time polynomial in |I| + b.
Proof. Let c : V (G) → [t] be a t-coloring of G. For every vertex v, deﬁne a set of ﬁlling colors
F (v) = {a + c(v)b + i : i = 0, . . . , b − |β(v)| − 1} and put
L′ (v) = L(v) ∪ F (v).
Let α : V (G) → 2[a] be an L-(a:β)-coloring of G. We deﬁne a coloring α′ : V (G) → 2[a+tb]
by setting α′ (v) = α(v) ∪ F (v) for every vertex v ∈ V (G). Observe that α′ (v) ⊆ L′ (v) and
|α′ (v)| = |α(v)| + (b − |β(v)|) = b. Since α was a proper L-(a:β)-coloring, adjacent vertices can only
share the ﬁlling colors. However, the lists of adjacent vertices have disjoint subsets of ﬁlling colors,
since these vertices are colored diﬀerently by c. It follows that α′ is an L′ -(a:b)-coloring of G.
Conversely, let α′ : V (G) → 2[a+tb] be an L′ -(a:b)-coloring of G. For every vertex v, we have
|α′ (v) ∩ [a]| = b − |α′ (v) ∩ F (v)| ≥ b − (b − |β(v)|) = |β(v)|. Deﬁne α(v) to be any cardinality β(v)
subset of α′ (v) ∩ [a]. It is immediate to check that α is an L-(a:β)-coloring of G.
We are now ready to prove one of our main results.
Theorem 3. If there is an algorithm for List (a:b)-coloring that runs in time 2o(log b)·n , then ETH
fails. This holds even if the algorithm is only required to work on instances where a = Θ(b2 log b)
and b = Θ(b(n)) for an arbitrarily chosen polynomial-time computable function b(n) such that
b(n) ∈ ω(1) and b(n) = O(n/ log n).
10

Proof. Let b(n) be a function as in the statement. We can assume w.l.o.g. that 2 ≤ b(n) ≤ n/ log2 n,
for otherwise we can replace b(n) with a function b′ (n) = 2+⌊b(n)/c⌋ in the reasoning below, where c
is a big enough constant; note that b′ (n) = Θ(b(n)). Fix a function g(b) = o(log b) and assume there
is an algorithm A for List (a:b)-coloring that runs in time 2g(b)·n , whenever b = Θ(b(n)). Consider
an instance of (3,4)-SAT with n variables. Let b = b(n). By Theorem 9 in poly(n) time we get an
equivalent instance (G, β, L) of Nonuniform List (a:(2b))-coloring such that a = Θ(b2 log b),
|V (G)| = O( logn b ), and a 3-coloring of G. Next, by Lemma 13 in poly(n) time we get an equivalent
instance (G, L′ ) of List ((a + 6b):(2b))-coloring. Finally, we solve the instance (G, L′ ) using
algorithm A. Since b(n) = ω(1), we have g(b(n)) = o(log(b(n))), and A runs in time 2o(log b(n))·|V (G)| .
o(log b(n))· log nb(n)
Thus, we have solved the instance φ of (3,4)-SAT in time 2o(log b(n))·|V (G)| = 2
= 2o(n) .
By Corollary 6, this contradicts ETH.

4

From List (a:b)-coloring to (a:b)-coloring

In this section we reduce List (a:b)-coloring to (a:b)-coloring. This is done by adding a Kneser
graph, and replacing the lists by edges to appropriate vertices of the Kneser graph. We will need
the following well-known property of Kneser graphs (see e.g., Theorem 7.9.1 in the textbook [15]).
Theorem 14. If p > 2q then every homomorphism from KGp,q to KGp,q is an automorphism.
We proceed with the reduction.
Lemma 15. For any given instance of List (a:b)-coloring
with n vertices, there exists an equiv
a+b
alent instance of ((a + b):b)-coloring with n + b vertices. Moreover, it can be computed in

poly(n, a+b
b )-time.
Proof. Let (G, L) be an instance of List (a:b)-coloring where G is a graph and L : V (G) → 2[a]

describes the lists of allowed colors. Deﬁne a graph K with V (K) = [a+b]
and
b
E(K) = { XY : X, Y ∈ V (K) and X ∩ Y = ∅ }.

That is, K is isomorphic to the Kneser graph KGa+b,b . Then let V ′ = V (G) ⊎ V (K) and
E ′ = E(G) ⊎ E(K) ⊎ { vX : v ∈ V (G) and X ∈ V (K) and L(v) ∩ X = ∅ }.

vertices, and the construction can be done in time polynomial
The graph G′ = (V ′ , E ′ ) has n+ a+b
b

a+b
′
in n+ b . Let G be our output instance of ((a+b):b)-coloring. We will show that it is equivalent
to the instance (G, L) of List (a:b)-coloring.

[a+b]
′
′
Let us assume that α : V (G) → [a]
b is an L-(a:b)-coloring of G. Consider α : V (G ) →
b
such that
(
α(v) for v ∈ V (G)

α′ (v) =
v
for v ∈ V (K) = [a+b]
.
b

We claim that α′ is an ((a + b):b)-coloring of G′ . Indeed, for every edge uv ∈ E(G) we have
α′ (u) ∩ α′ (v) = α(u) ∩ α(v) = ∅ because α is an L-(a:b)-coloring of G. For every edge XY ∈ E(K)
we have α′ (X) ∩ α′ (Y ) = X ∩ Y = ∅. For every edge vX ∈ E(V (G), V (K)) we have α′ (v) ∩ α′ (X) =
α(v) ∩ X ⊆ L(v) ∩ X = ∅.

Now, let us assume that α′ : V (G′ ) → [a+b]
is an ((a + b):b)-coloring of G′ . Recall that α′ is a
b
′
′
homomorphism of G to KGa+b,b . Denote φ = α |V (K) . By Theorem 14, φ is an automorphism of K.
11

Deﬁne α′′ = φ−1 ◦ α′ . Then α′′ is an ((a + b):b)-coloring of G′ with the property that α′′ (X) = X for
every X ∈ V (K). We claim that α′′ |V (G) is an L-(a:b)-coloring of G. Since α′′ is a ((a+b):b)-coloring
of G′ , it suﬃces to show that α′′ (v) ⊆ L(v) for every vertex v ∈ V (G). Pick a color γ 6∈ L(v). Let
Xγ be the b-element set consisting of γ and arbitrary b − 1 elements from [a + b] \ ([a] ∪ {γ}). Then
L(v) ∩ Xγ = ∅ and hence vXγ ∈ E(G′ ). It follows that Xγ ∩ α′′ (v) = α′′ (Xγ ) ∩ α′′ (v) = ∅, and in
particular γ 6∈ α′′ (v). Thus, α′′ (v) ⊆ L(v) as required.
We now prove our main result.
Theorem 1. If there is an algorithm for (a:b)-coloring that runs in time f (b) · 2o(log b)·n , for
some computable function f (b), then ETH fails. This holds even if the algorithm is only required to
work on instances where a = Θ(b2 log b).
Proof. Fix a computable function f (b), a function g(b) = o(log b) and assume there is an algorithm
A for (a:b)-coloring that runs in time f (b) · 2g(b)·n for a given n-vertex graph, whenever a =
Θ(b2 log b). Without loss of generality we can replace f (b) by any non-decreasing function f ′ (n)
such that f ′ (n) ≥ f (n) and f ′ (n) > n. Intuitively, we now deﬁne an unbounded function b(N )
N
which should be at least 2, at most the inverse of f , and small enough so that 2O(b log b) ≤ log
b . The
following function is ω(1) and a standard argument shows how to compute it in poly(N ) time (see
Lemmas 3.2 and 3.4 in [4]).
b(N ) = min (max{b : f (b) ≤ N } , max{b : b log b ≤ log N/ log log N }) + 2.
Consider an instance of (3,4)-SAT with N variables. Let b = b(N ). By Theorem 9 in poly(N )
time we get an equivalent instance (G, β, L) of Nonuniform List (a:(2b))-coloring such that
N
a = Θ(b2 log b), |V (G)| = O( log
b ), and a 3-coloring of G. Next, by Lemma 13 in poly(N ) time we
′ ) of List ((a + 6b):(2b))-coloring. Then, by Lemma 15, in time
get an equivalent
instance
(G,
L

a+8b
poly(N, 2b ) = poly(N ) we get an equivalent instance G′ of ((a + 8b):(2b))-coloring such that

2
|V (G′ )| = |V (G)| + a+8b
2b . Observe that since a = Θ(b log b) and b log b ≤ log N/ log log N ,
a+8b
≤ (a + 8b)2b = 2O(b log b) = 2O(log N/ log log N ) = N o(1) = o(N/log b(N ))
2b
N
′
Hence |V (G′ )| = O( log
b ). Finally, we solve the instance G using algorithm A. Since b(N ) = ω(1),
we have g(b(N )) = o(log(b(N ))). Therefore, A runs in time
′

f (b) · 2o(log b(N ))·|V (G )| ≤ N · 2o(log b(N ))·O(N/ log b(N )) = 2o(N )
solving the instance φ of (3,4)-SAT in time 2o(N ) . By Corollary 6, this contradicts ETH.
Corollary 2. If there is an algorithm for Graph Homomorphism that runs in time f (h) ·
2o(log log h)·n , for some computable function f (h), then ETH fails. This holds even if the algorithm
is only required to work on instances where H is a Kneser graph KGa,b with a = Θ(b2 log b).
Proof. Fix a computable function f (h) and assume there is an algorithm A for Graph Homomorphism that runs in time f (h) · 2o(log log h)·n for a given n-vertex graph, whenever H is a Kneser
graph Ka,b with a = Θ(b2 log b). Consider an instance of (a:b)-coloring with
n vertices and

a = Θ(b2 log b). This is an instance of Graph Homomorphism with h = ab ≤ ab = 2O(b log b) ,
hence A solves it in
f (h) · 2o(log log h)·n = f (2O(b log b) ) · 2o(log(b log b))·n ≤ f ′ (b) · 2o(log b)·n
for some computable function f ′ (b) ≥ f (2Θ(b log b) ), which contradicts Theorem 1.
12

5

Low-degree testing

In this section we derive lower bounds for (r, k)-Monomial Testing. In this problem, we are
given an arithmetic circuit C over some ﬁeld F; such a circuit may contain input, constant, addition,
negation, multiplication, and inversion gates. One gate is designated to be the output gate, and
it computes some polynomial P of the variables x1 , x2 , . . . , xn that appear in the input gates. We
assume that P is a homogenous polynomial of degree k, i.e., all its monomials have total degree k.
The task is to verify whether P contains an r-monomial, i.e., a monomial in which every variable
has its individual degree bounded by r, for a given parameter r ≤ k. Abasi et al. [1] gave a very
fast randomized algorithm for (r, k)-Monomial Testing.
Theorem 16 (Abasi et al. [1]). Fix integers r, k with 2 ≤ r ≤ k. Let p ≤ 2r 2 + 2r be a prime,
and let g ∈ GF(p)[x1 , . . . , xn ] be a homogenous polynomial of degree k, computable by a circuit C.
Then, there is a randomized algorithm running in time O(r 2k/r |C|(rn)O(1) ) which
• with probability at least 1/2 answers YES when g contains an r-monomial,
• always answers NO when g contains no r-monomial.
This result was later derandomized by Gabizon et al. [14] under the assumption that the circuit
is non-cancelling, that is, it contains only input, addition, and multiplication gates. Many concrete
problems like r-Simple k-Path can be reduced to (r, k)-Monomial Testing by encoding the set
of candidate objects as monomials of some large polynomial, so that “good” objects correspond to
monomials with low individual degrees. As we will see in a moment, this is also the case for List
(a:b)-coloring.
Let (G = (V, E), L) be an instance of the List (a:b)-coloring problem and let I be the family
of all independent sets of G. We denote n = |V |. Let Ca (G, L) denote the set of all functions
c : V → 2[a] such that for every edge uv ∈ E the sets c(u) and c(v) are disjoint, and for every
vertex v we have c(v) ⊆ L(v). Consider the following polynomial in n(a + 1) variables {xv }v∈V and
{yv,j }v∈V,j∈[a] , over GF(2).
pG =

X

Y

x|c(v)|
v

c∈Ca (G,L) v∈V
P
v |c(v)|=bn

Y

yv,j .

(1)

j∈c(v)

Note that every summand in expression (1) has a diﬀerent set of variables, therefore it corresponds to a monomial (with coeﬃcient 1). Then the following proposition is immediate.
Proposition 17. There is a list (a:b)-coloring of graph G iff pG contains a b-monomial.
Now we show that pG can be evaluated relatively fast.
Lemma 18. The polynomial pG can be evaluated using a circuit of size 2n poly(a, n), which can be
constructed in time 2n poly(a, n)
Proof. Consider the following polynomial:
qG =

a XY
Y

xv yv,j .

(2)

j=1 I∈I v∈I

Observe that pG is obtained from qG by removing all monomials of degree diﬀerent than 2bn. Eq. (2)
shows that qG can be evaluated by a circuit Cq of size |I| poly(a, n) ≤ 2n poly(a, n), which can be
13

constructed in time 2n poly(a, n). We obtain from Cq a circuit Cp for pG by splitting gates according
to degrees, in a bottom-up fashion, as follows.
Every input gate u of Cq is replaced with a gate u1 in Cp . Every addition gate u with inputs
x and y in Cq is replaced in Cp by 2an addition gates u1 , . . . , u2an , where ui has inputs xi and yi
(whenever xi and yi exist). Every multiplication gate u with inputs x and y in Cq is replaced in Cp
by 2an addition gates u1 , . . . , u2an . Moreover, for every pair of integers 1 ≤ r, s ≤ 2an we create a
multiplication gate ur,s with inputs xr and ys (whenever they exist) and make it an input of the
addition gate ur+s . It is easy to see that for every gate u of Cq , for every i, the gate ui of Cp evaluates
the same polynomial as u, but restricted to monomials in which the total degree is equal to i. When
o is the output gate of Cq , then o2bn is the output gate of Cp . Clearly, |Cp | ≤ (2an + 1)2 |Cq |, and
Cp can be constructed from Cq in time 2n poly(a, n).
Since pG is a homogenous polynomial of degree k = 2bn, by putting r = b we can combine
Proposition 17, Theorem 16 and Lemma 18 to get yet another polynomial-space algorithm for List
(a:b)-coloring, running in time bO(n) · poly(n). Similarly, if the running time in Theorem 16
was improved from to 2o(log r/r)·k · |C| poly(r, n), then we would get an algorithm for List (a:b)coloring in time 2o(log b)·n · poly(n), which contradicts ETH by Theorem 3. However, a careful
examination shows that
pthis chain of reductions would only yield instances of (r, k)-Monomial
Testing with r = O( k/ log k). Hence, this does not exclude the existence of a fast algorithm
that works only for large r. Below we show a more direct reduction, which excludes fast algorithms
for a wider spectrum of pairs (r, k).
In the Carry-Less Subset Sum problem, we are given n + 1 numbers s, a1 , . . . , an , each
represented as n decimal digits. For any number x, the j-th decimal digit of x is denoted by x(j) .
P
(j)
It is assumed that ni=1 ai < 10, for every j = 1, . . . , n. The goal is to verify whether there is
P
a sequence of indices 1 ≤ i1 < . . . < ik ≤ n such that kq=1 aiq = s. (Note that by the small
P
(j)
sum assumption, this is equivalent to the statement that kq=1 aiq = s(j) , for every j = 1, . . . , n).
The standard NP-hardness reduction from 3-SAT to Subset Sum in fact outputs an instance of
Carry-Less Subset Sum of linear size, yielding the following.
Lemma 19. Unless ETH fails, there is no algorithm that solves Carry-Less Subset Sum with n
numbers in time 2o(n) .
Proof. Let ϕ be an instance of 3-SAT with N variables and M clauses. By a standard NP-hardness
reduction for Subset Sum (see e.g. the textbook of Cormen et al. [8]) in polynomial time one can
build an equivalent instance of Carry-Less Subset Sum, with O(N +M ) numbers, each having of
O(N + M ) decimal digits, and with the sum of j-th digit in all the numbers not exceeding 7. In case
the number of numbers is diﬀerent from the length of their decimal representations, we can make
them equal by padding the instance by zero numbers or with zeroes in the decimal representations.
Thus, by Theorem 4, an 2o(n) algorithm for Carry-Less Subset Sum would contradict ETH.
We proceed to reducing Carry-Less Subset Sum to (r, k)-Monomial Testing. Let us
choose a parameter t ∈ {1, . . . , n}. We assume w.l.o.g. that n mod t = 0, for otherwise we add
t − (n mod t) zeroes at the end of every input number. Let q = n/t. For an n-digit decimal number
x, for every j = 1, . . . t, let x[j] denote the q-digit number given by the j-th block of q digits in x,
i.e.,
x[j] = (x(jq−1) · · · x((j−1)q) )10 .

14

Let r = 10q − 1. Deﬁne the following polynomial over GF(2):


n
t
t
[j]
Y
Y
Y
[j]
ai


xjr−s .
qS =
xj
·
yi + zi ·
i=1

j=1

j=1

Proposition 20.
) is a YES-instance of Carry-Less Subset Sum iff qS contains
1 , . . . , anQ
Q (s, aQ
the monomial tj=1 xrj i6∈S yi i∈S zi , for some S ⊆ {1, . . . , n}.
Proof. Consider the following polynomial over GF(2):
rS =

X

t
Y

P

xj

i∈S

S⊆{1,...,n} j=1

[j]

ai +r−s[j]

Y

i6∈S

yi

Y

zi .

i∈S

The summands in the expression above have unique sets of yi variables, so each of them corresponds
to a monomial (of coeﬃcient 1). It is clear that these monomials where for every j the degree of
xj is exactly r are in one-to-one correspondence with solutions of the instance (s, a1 , . . . , an ). The
claim follows by observing that polynomials rS and qS coincide.
Let pS denote the polynomial obtained from qS by ﬁltering out all the monomials of degree
diﬀerent than k = tr + n.
Proposition 21. (s, a1 , . . . , an ) is a YES-instance of Carry-Less Subset Sum iff pS contains
an r-monomial.
Proof. If (s, a1Q
, . . . , an )Qis a YES-instance
and let then by Proposition 20 polynomial qS contains
Q
t
r
the monomial j=1 xj i6∈S yi i∈S zi , which is an r-monomial. This monomial has degree tr + n,
so it is contained in pS as well.
Conversely, assume pS contains an r-monomial m. Every monomial of qs (and hence also of pS )
contains exactly one of the variables yi and zi , with degree 1, for every i = 1, . . . , n. It means that
the total degree of xj -type variables in m is tr. Hence,
since
an r-monomial, each of xj ’s has
Q m isQ
Qt
r
degree exactly r. In other words, m is of the form j=1 xj i6∈S yi i∈S zi , for some S ⊆ {1, . . . , n}.
Then (s, a1 , . . . , an ) is a YES-instance of Carry-Less Subset Sum by Proposition 20.
Proposition 22. pS can be evaluated by a circuit of size O(nt2 r + n2 t), which can be constructed
in time polynomial in n + t + r.
Proof. Polynomial qS can be evaluated by a circuit of size O(nt). The circuit for pS is built using
the construction from Lemma 18. Thus, its size is O(nt(tr + n)) = O(nt2 r + n2 t).
We are ready to give our main lower bound for (r, k)-Monomial Testing. We state it in
the most general form, which unfortunately is also quite technical. Next, we derive an exemplary
corollary that gives a lower bound for r expressed as a function of k.
Theorem 23. If there is an algorithm solving (r, k)-Monomial Testing in time 2o(k log r/r) |C|O(1) ,
then ETH fails. The statement remains true even if the algorithm works only for instances where
r = 2Θ(n/t(n)) and k = t(n)2Θ(n/t(n)) , for an arbitrarily chosen function t : N → N computable in
2o(n) time, such that t(n) = ω(1) and t(n) ≤ n for every n.

15

Proof. By Lemma 19, it suﬃces to give an algorithm for Carry-Less Subset Sum that works in
time 2o(n) , where n is the number of input numbers. Let t = t(n) and q = n/t, r = 10q −1, k = tr+n
as before. Note that r = 2Θ(n/t(n)) . Also, since 10n/t(n) = Ω(n/t(n)), k = Θ(t(n)10n/t(n) + n) =
Θ(t(n)10n/t(n) ) = t(n)2Θ(n/t(n)) .
By Proposition 21, solving Carry-Less Subset Sum is equivalent to detecting an r-monomial
in pS , which is a homogenous polynomial of degree k = tr + n. Let C be the circuit for pS ; by
Proposition 22 we have |C| = O(nt2 r + n2 t). If this can be done in time 2o(k log r/r) |C|O(1) , we get
an algorithm for Carry-Less Subset Sum running in time
q

2o(k log r/r) |C|O(1) = 2o((tr+n)q/r) (ntr)O(1) = 2o(n+nq/10 ) (ntr)O(1) = 2o(n) (ntr)O(1) .
Recall that t ≤ n and r = 10n/t − 1 = 2o(n) , since t = t(n) = ω(1). Hence (ntr)O(1) = 2o(n) poly(n).
The claim follows.
Theorem 24. Let σ ∈ [0, 1). Then, unless ETH fails, there is no algorithm for (r, k)-Monomial
log r
Testing that solves instances with r = Θ(kσ ) in time 2o(k· r ) · |C|O(1) .
Proof. We prove that an algorithm for (r, k)-Monomial Testing with properties as in the statement can be used to derive an algorithm for the same problem with properties as in the statement
of Theorem 23, which implies that ETH fails. Take t to be a positive integer not larger than n such
that
10n/t − 1
1
≤
≤ 2;
(3)
2
(t · (10n/t − 1) + n)σ
it can be easily veriﬁed that since σ < 1, for large enough n such an integer t ≤ n always exists.
Moreover, we have that t = t(n) ∈ ω(1) and t(n) can be computed in polynomial time by brute-force.
Hence, t(n) satisﬁes the properties stated in Theorem 23.
Let t = t(n) and q = n/t. Deﬁne r = 10q − 1 and k = tr + n, then (3) is equivalent to
1/2 ≤ r/k σ ≤ 2.
Hence r = Θ(kσ ). Consequently, the assumed algorithm solves (r, k)-Monomial Testing in time
2o(k log r/r) |C|O(1) , however in the proof of Theorem 23 we have shown that the existence of an
algorithm that achieves such a running time for this particular choice of parameters implies that
ETH fails.
Note that Theorem 24 in particular implies that (r, k)-Monomial Testing does not admit an
log r
algorithm that achieves running time 2o( r )·k · |C|O(1) for any given r.
Acknowledgements. The authors thank Andreas Björklund and Matthias Mnich for sharing the
problem considered in this paper.

16

References
[1] H. Abasi, N. H. Bshouty, A. Gabizon, and E. Haramaty. On r-simple k-path. In MFCS 2015,
volume 8635 of Lecture Notes in Computer Science, pages 1–12. Springer, 2014.
[2] A. Björklund, T. Husfeldt, and M. Koivisto. Set partitioning via inclusion-exclusion. SIAM J.
Comput., 39(2):546–563, 2009.
[3] N. H. Bshouty. Optimal algorithms for the coin weighing problem with a spring scale. In COLT
2009, 2009.
[4] L. Cai, J. Chen, R. G. Downey, and M. R. Fellows. On the structure of parameterized problems
in NP. Inf. Comput., 123(1):38–49, 1995.
[5] M. G. Christ, L. M. Favrholdt, and K. S. Larsen. Online multi-coloring with advice. In WAOA
2014, volume 8952 of Lecture Notes in Computer Science, pages 83–94. Springer, 2014.
[6] V. Chvátal. Mastermind. Combinatorica, 3(3):325–329, 1983.
[7] V. Chvátal, M. Garey, and D. Johnson. Two results concerning multicoloring. In Algorithmic
Aspects of Combinatorics, volume 2 of Annals of Discrete Math., pages 151–154. Elsevier, 1978.
[8] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The
MIT Press, 2009.
[9] M. Cygan, F. V. Fomin, A. Golovnev, A. S. Kulikov, I. Mihajlin, J. Pachocki, and A. Socała.
Tight bounds for Graph Homomorphism and Subgraph Isomorphism. In SODA 2016, pages
1643–1649, 2016.
[10] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and
S. Saurabh. Parameterized Algorithms. Springer, 2015.
[11] R. Diestel. Graph Theory. Springer-Verlag Heidelberg, 2010.
[12] D. C. Fisher. Fractional colorings with large denominators. J. Graph Theory, 20(4):403–409,
1995.
[13] F. V. Fomin, P. Heggernes, and D. Kratsch. Exact algorithms for graph homomorphisms.
Theory Comput. Syst., 41(2):381–393, 2007.
[14] A. Gabizon, D. Lokshtanov, and M. Pilipczuk. Fast algorithms for parameterized problems
with relaxed disjointness constraints. In ESA 2015, volume 9294 of Lecture Notes in Computer
Science, pages 545–556. Springer, 2015.
[15] C. Godsil and G. F. Royle. Algebraic Graph Theory. Springer, 2001.
[16] V. Grebinski and G. Kucherov. Optimal reconstruction of graphs under the additive model.
Algorithmica, 28(1):104–124, 2000.
[17] M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in
combinatorial optimization. Combinatorica, 1(2):169–197, 1981. Corrigendum available at:
http://dx.doi.org/10.1007/BF02579139.

17

[18] M. M. Halldórsson and G. Kortsarz. Multicoloring: Problems and techniques. In MFCS 2013,
volume 3153 of Lecture Notes in Computer Science, pages 25–41. Springer, 2004.
[19] M. M. Halldórsson, G. Kortsarz, A. Proskurowski, R. Salman, H. Shachnai, and J. A. Telle.
Multicoloring trees. Inf. Comput., 180(2):113–129, 2003.
[20] F. Havet. Channel assignment and multicolouring of the induced subgraphs of the triangular
lattice. Discrete Math., 233(1-3):219–231, 2001.
[21] P. Hell and J. Nešetřil. On the complexity of H -coloring. J. Comb. Theory, Ser. B, 48(1):92–
110, 1990.
[22] Q. Hua, Y. Wang, D. Yu, and F. C. M. Lau. Dynamic programming based algorithms for
set multicover and multiset multicover problems. Theor. Comput. Sci., 411(26-28):2467–2474,
2010.
[23] R. Impagliazzo and R. Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367–
375, 2001.
[24] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity?
J. Comput. Syst. Sci., 63(4):512–530, 2001.
[25] M. Kchikech and O. Togni. Approximation algorithms for multicoloring planar graphs and
powers of square and triangular meshes. Discrete Math. Theor. Comput. Sci., 8(1):159–172,
2006.
[26] F. Kuhn. Local multicoloring algorithms: Computing a nearly-optimal TDMA schedule in
constant time. In STACS 2009, volume 3 of LIPIcs, pages 613–624. Schloss Dagstuhl - LeibnizZentrum fuer Informatik, Germany, 2009.
[27] W. Lin. Multicoloring and Mycielski construction. Discrete Math., 308(16):3565 – 3573, 2008.
[28] B. Lindström. On a combinatorial problem in number theory. Canad. Math. Bull, 8(4):477–490,
1965.
[29] L. Lovász. Kneser’s conjecture, chromatic number, and homotopy. J. Comb. Theory, Ser. A,
25(3):319–324, 1978.
[30] D. Marx. The complexity of tree multicolorings. In MFSC 2002, volume 2420 of Lecture Notes
in Computer Science, pages 532–542. Springer, 2002.
[31] C. McDiarmid and B. A. Reed.
36(2):114–117, 2000.

Channel assignment and weighted coloring.

Networks,

[32] J. W. Moon and L. Moser. On cliques in graphs. Israel J. Math., 3(1):23–28, 1965.
[33] J. Nederlof.
Inclusion exclusion for hard problems.
Master’s thesis, Department of Information and Computer Science, Utrecht University, 2008.
Available at
http://www.win.tue.nl/~jnederlo/MScThesis.pdf.
[34] K. S. Sudeep and S. Vishwanathan. A technique for multicoloring triangle-free hexagonal
graphs. Discrete Math., 300(1-3):256–259, 2005.

18

[35] C. A. Tovey. A simpliﬁed NP-complete satisﬁability problem. Discrete Appl. Math., 8(1):85–89,
1984.
[36] M. Wahlström. New plain-exponential time classes for graph homomorphism. Theory Comput.
Syst., 49(2):273–282, 2011.

19

