Sophie Prefix

Jean-François Culus
email: jean-francois-culus@espe-martinique.fr

How Far From a Worst Solution a Random Solution of a CSP Instance Can Be?

Keywords:

Given an instance I of an optimization constraint satisfaction problem (CSP), finding solutions with value at least the expected value of a random solution is easy. We wonder how good such solutions can be. Namely, we initiate the study of ratio where , and refer to respectively the optimal, the worst, and the average solution values on I. We here focus on the case when the variables have a domain of size and the constraint arity is at most , where k, q are two constant integers. Connecting this ratio to the highest frequency in orthogonal arrays with specified parameters, we prove that it is if , where is the smallest prime power such that otherwise, and in -partite instances.

How Far From a Worst Solution a Random Solution of a k CSP Instance Can Be? 1 Introduction

Given an integer q ≥ 2, an optimization Constraint Satisfaction Problem (CSP) over Z q = Z/qZ considers a set {x 1 , . . . , x n } of Z q -valued variables and a set {C 1 , . . . , C m } of constraints, where a constraint consists of the application of a (non constant) predicate P i : Z ki q → {0, 1} to a tuple x Ji = (x i1 , . . . , x i k i ) of variables. The goal is then to assign values to the variables so as to satisfy either as many, or as few constraints as possible. For instance, in the Maximum Satisfiability Problem (Max Sat), the goal is to satisfy as many disjunctive clauses as possible. In Min Lin-q, the goal is to satisfy as few equations of a system of linear equations modulo q as possible.

Most often, a positive weight w i is associated with each constraint C i . Given a positive integer N , we represent by [N ] the discrete interval {1, . . . , N}. The goal is then to optimize an objective function of the form m i=1 w i C i = m i=1 w i P i (x Ji ) = m i=1 w i P i (x i1 , . . . , x i k i ) over Z n q where for all i ∈ [m], k i ∈ [n], P i : Z ki q → {0, 1}, J i = (i 1 , . . . , i ki ) ⊆ [n] and w i > 0. The special case when functions P i all belong to a specific family F of functions is referred to as CSP(F) in the literature. Given a predicate P , the restriction to constraints of the form P (x Ji + v i ) where v i is a constant vector is referred to as CSP-P. For example, given a positive integer k, XOR k is the k-ary boolean predicate that accepts entries (y 1 , . . . , y k ) with y 1 + . . . + y k ≡ 1 mod 2; then Lin-2

= CSP-{XOR k | k ∈ N * } = CSP({XOR k , 1 -XOR k | k ∈ N * }).
We here consider the slight generalization where functions P i may be realvalued. In the sequel, we denote by CSP-q the corresponding problem, and by k CSP-q (resp., Ek CSP-q) the special case when every constraint depends on at most (resp., exactly) k variables, where k is a universal constant integer. As k CSP-q is NP-hard even in case when q = k = 2 [START_REF] Garey | Some simplified NP-complete graph problems[END_REF], a major issue as regards optimization CSPs consists in charactering their approximation degree.

Around the Average Solution Value

Thereafter, given an instance I of CSP-q, we denote by v(I, .) its objective function, by w(I) = m i=1 w i the total weight on I, by opt(I) and wor(I) respectively the optimum and the worst solution values on I. It is convenient to think of the average solution value on I as the expected value E X [v(I, X)] of a random solution where X = (X 1 , . . . , X n ) is a vector of pairwise independent random variables, each uniformly distributed over Z q . This value expresses as

E X [v(I, X)] = m i=1 w i E X [P i (X Ji )] = m i=1 w i r Pi
where given i ∈ [m], r Pi refers to the average value of P i over Z ki q . For example, on an instance I of Lin-2, the average solution value equals w(I)/2.

Solutions with value at least E X [v(I, X)] are computationally easy to find, e.g. using the conditional expectation technique [START_REF] Johnson | Approximation algorithms for combinatorial problems[END_REF]. Therefore, two questions can naturally be asked: is it possible to compute within polynomial time solutions that beat the average solution value, and what is the gain of the average solution value over the worst solution value?

The former question notably leads to the concept of approximation of the advantage over a random assignment [START_REF] Håstad | On the advantage over a random assignment[END_REF], herein referred to as gain approximation. The advantage of a given solution x over a random assigment is the differ-

ence v(I, x) -E X [v(I, X)] if one maximizes, E X [v(I, X)] -v(I, x) if one mini- mizes. Given ρ ∈]0, 1], x approximates the optimum gain |opt(I) -E X [v(I, X)]| over E X [v(I, X)] within factor ρ iff x achieves a gain ratio ρ G (I, x) = v(I, x) -E X [v(I, X)] opt(I) -E X [v(I, X)] (1)
at least ρ. A given CSP Π is ρ-gain approximable (where ρ possibly depends on parameters of the considered instance I) if it is possible to compute within polynomial time on every instance I of Π a solution with gain ratio at least ρ(I).

The corresponding issue consists in determining "the best" ρ for which Π is ρgain approximable. Håstad and Venkatesh introduced in [START_REF] Håstad | On the advantage over a random assignment[END_REF] this approximation measure motivated by the fact that for numerous predicates P , for all constant ε > 0, finding solutions with value at least (r P + ε)w(I) on almost satisfiable instances of Max CSP-P is NP-hard. For example, for all k ≥ 3, XOR k is such a predicate [START_REF] Håstad | Some optimal inapproximability results[END_REF]. Thus for all k ≥ 3, k Lin-2 is NP-hard to approximate to within any constant gain factor. It is, though, approximable within an expected gain factor of Ω( 1/m) [START_REF] Håstad | On the advantage over a random assignment[END_REF]. The latter question leads to the notion of advantage of a random solution over the worst solution value. Namely, we say that the average solution value on

I is ρ-approximate if the ratio ρ E (I) = E X [v(I, X)] -wor(I) opt(I) -wor(I) (2)
of the gain of E X [v(I, X)] over wor(I) to the diameter of I is at least ρ. Given a CSP Π, we say that the average solution value is ρ-approximate for Π provided that ρ E (I) ≥ ρ(I) holds for all instances I of Π. The issue here consists in exhibiting "the tightest" possible lower bound ρ for ρ E . For example, on an instance I of E3 Lin-2, as given any x, any equation is satisfied either by x or by its complement, we have opt(I) + wor(

I) = w(I) = 2 × E X [v(I, X)] [5].
Equivalently, ρ E (I) is equal to 1/2. By contrast, for E2 Lin-2, we show that ρ E (I) ∈ Ω(1/n), while there are satisfiable instances I on which ρ E (I) ∈ Θ(1/n). Figure 1 pictures the quantities involved in ratios ( 1) and ( 2). The two questions are complementary, and the latter has potential to enlighten the former. For instance, we may think that the more E X [v(I, X)] does a good job at getting away from wor(I), the more it is computationally difficult to get away from it.

wor(I) o p t ( I) E X [v(I, X)] v(I, x)

Outline

Our goal is to estimate ρ E (I) on instances I of k CSP-q given two integers q ≥ 2, k ≥ 2. To the best of our knowledge, such a study has not been carried out so far. We may nevertheless make mention of a result due to Feige et al., and that concerns the restriction to submodular functions. Given a positive integer n, a function P : {0, 1} n → R is submodular iff it satisfies:

P (y) + P (z) ≥ P (y 1 ∨ z 1 , . . . , y n ∨ z n ) + P (y 1 ∧ z 1 , . . . , y n ∧ z n ), y, z ∈ {0, 1} n
As shown in [START_REF] Feige | Maximizing non-monotone submodular functions[END_REF], given any maximizer x * of such a function P , we have: In k CSP-q, thought, the functions that occur in the constraints are only required to have arity at most k. In order to exhibit lower bounds for ρ E (I), we seek expressions of E X [v(I, X)] as a conical combination of the optimum solution value and as few other solution values as possible. We adopt kind of a neighbourhood approach: we associate with each solution x of I a multisubset S(I, x) of solutions with the same average solution value as the whole solution set, of relatively small size, and in which x occurs at least once. In the next section, we show how to derive such solution multisets from hypothetical orthogonal arrays (see Definition 2) with specified parameters that rely on characteristics of I (main theorem). In Sect. 3, we derive lower bounds for ρ E either from orthogonal arrays of the literature, or by reduction to CSPs over a bigger alphabet. These bounds are summarized in Table 1. In the last section, we briefly discuss the obtained results and perspectives for further research.

Table 1. Lower bounds for ρE on instances of k CSP-q given two integers q ≥ 2, k ≥ 2: p κ refers to the smallest prime power greater than or equal to q.

q k restriction ρE ≥ 2 ≥ 2 (k + 1)-partite instances of k CSP-q 1/q k ≥ 2 < p κ (p κ + 1)-partite instances of k CSP-q Ω(1/q k ) ≥ 3 = 3 (2 log 2 q + 2)-partite instances of 3 CSP-q Ω(1/q 3 ) = 2 ≥ 2 k CSP-2 Ω(1/n k/2 ) ≥ 3 ≥ 2 k CSP-q Ω(1/n k-1-log p κ (k-1) )

Seeking Symmetries in the Solution Set

Let us start with a simple example. Given an integer q ≥ 2, we denote by O q the set of functions P : Z k q → R with k ∈ N * that satisfy:

q-1 a=0 P (y 1 + a, . . . , y k + a)/q = r P , y∈ Z k q (4)
O q is a natural generalization to q-ary alphabets of such boolean functions P as XOR 3 that, when using a {-1, 1}-encoding of truth values, are odd. For example, the predicate on Z 3 q that accepts solutions to equation y 1 + y 2y 3 ≡ 0 mod q is a function of O q . By (4), given any instance I of CSP(O q ), we have:

v(I, x)/q + q-1 a=1 v(I, (x 1 + a, , . . . , x n + a))/q = E X [v(I, X)], x ∈ Z n q (5)
Taking ( 5) at a solution x with optimal value, one trivially gets that the average value is 1/q-approximate on I. Hence, for this particular CSP, one shall define S(I, x) by S(I, x) = {x + (a, . . . , a) | a ∈ Z q }.

Partition-Based Solution Multisets

We base our solution multisets S(I, x), x ∈ Z n q on a specific partition V = {V 1 , . . . , V ν } of [n]. Our solution multisets then rely on an array M with ν columns and coefficients in Z q : given x ∈ Z n q , each row M r = (M 1 r , . . . , M ν r ) of M gives rise in S(I, x) to the vector obtained from x by translating for each c ∈ [ν] by M c r all its coordinates with index in V c . Formally, let R refer to the number of rows in the array, and let π V : Z ν q → Z n q be defined by:

π V (u) Vc = (u c , u c , . . . , u c ), c ∈ [ν] , u∈ Z ν q (6)
Then we define S(I, .) by:

S(I, x) = (x + π V (M r ) | r ∈ [R]) , x ∈ Z n q (7)
We more specifically are interested in pairs (V, M) that satisfy:

R r=1 P i (x Ji + π V (M r ) Ji )/R = r Pi , i∈ [m], x ∈ Z n q (8)
For example, when I is an instance of CSP(O q ), we may consider the pair (V, M) where V = {[n]} and M = (0, 1, . . . , q -1) T . Requirement [START_REF] Hedayat | Orthogonal Arrays: Theory and Applications[END_REF] ensures that for all solutions x of I, the average solution value over S(I, x) equals the average solution value on I. Since this holds for all x ∈ Z n q , this in particular holds in case when x is optimal. If R * refers to the number of times (0, . . . , 0) occurs as a row in M , then R * precisely is the number of times x occurs in S(I, x). Hence, provided that x is optimal, we have:

E X [v(I, X)] = R r=1 v(I, x * + π V (M r ))/R = R * × v(I, x * )/R + r∈[R]:Mr =(0,...,0) v(I, x * + π V (M r ))/R
We deduce that the average solution value on I is R * /R-approximate.

Therefore, we shall seek such pairs (V, M) on which the ratio R * /R is as high as possible. Observe that we may always assume that (0, . . . , 0) is a vector of highest frequency in M , due to the fact that given any u ∈ Z ν q , the array obtained by shifting every row of M by u still satisfies (8).

Solution Multisets Derived from Orthogonal Arrays

Given i ∈ [m], we denote by (c i,1 , . . . , c i,ki ) the sequence of indices in [ν] such that (i 1 , . . . , i ki ) ∈ V ci,1 × . . . × V c i,k i . Given any x ∈ Z n q , over S(I, x), P i is evaluated at entries x Ji + π V (M r ) Ji = (x i1 + M ci,1 r , . . . , x i k i + M c i,k i r ), r∈ [R]
(V, M) therefore in particular satisfies (8) at (i, x) provided that these entries coincide the same number of times with each u ∈ Z ki q . Equivalently, ( 8) is satisfied at (i, x) provided that each u ∈ Z ki q occurs R/q ki times in vector multiset

((M ci,1 r , . . . , M c i,k i r ) | r ∈ [R]) (9)
On the one hand, this may not occur unless indices c i,1 , . . . , c i,ki are pairwise distinct. On the other hand, assuming that these indices indeed are pairwise distinct, {c i,1 , . . . , c i,ki } can be any at most k-cardinality subset of [ν]. These observations suggest to consider a pair (V, M) where V is a strong coloring of the primary hypergraph of I, and M is orthogonal of strength k: Table 2. An OA(27, 5, 3, 2) on Z3 (we picture the transpose).

M 1 M 2 M 3 M 4 M 5 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 2 0 1 1 1 2 2 1 1 2 0 0 2 0 1 2 0 1 2 1 2 2 0 0 1 0 0 2 1 0 1 2 1 2 1 2 1 2 2 0 0 0 1 1 2 0 1 0 2 1 2 0 0 0 2 1 1 2 2 0 1 2 0 1 0 2 1 2 1 0 1 1 2 0 2 0 2 1 0
Definition 1. The primary hypergraph of a CSP instance I is the hypergraph G I where: for each j ∈ [n], there is a vertex j in G I ; for each i ∈ [m], there is a hyperedge

e i = (i 1 , . . . , i ki ) in G I . A strong coloring of G I is a partition {U 1 , . . . , U ν } of [n] such that for all c ∈ [ν] and all i ∈ [m], |U c ∩{i 1 , . . . , i ki }| ≤ 1.
I is said ν-partite whenever such a partition exists. Definition 2. Let q ≥ 2, t ≥ 1, ν ≥ t and R be four integers, and Σ be a set of q symbols. Then an R × ν array M with coefficients in Σ is an Orthogonal Array of strength t, OA(R, ν, q, t) in short, if given any sequence J = (c 1 , . . . , c t ) of t column indices, each v ∈ Σ t occurs the same number of times as a row in subarray M J = (M c1 , . . . , M c k ). (See Table 2 for an illustration.)

Since k i ≤ k, i ∈ [m]
, such a pair (V, M) indeed satisfies for all i ∈ [m] that the vectors of (9) coincide R/q ki times with each u ∈ Z ki q and thus, [START_REF] Hedayat | Orthogonal Arrays: Theory and Applications[END_REF]. It is possible to reduce the number of columns and possibly the strength of the array if functions P i all satisfy, for some integer t > 0, that their average value when fixing any t of their variables is equal to their average value. Namely, given two integers q ≥ 2, t ≥ 1, we define I t q as the set of functions P : Z k → R with k ∈ N * that satisfy:

y∈Z k q :yJ =v P (y)/q k-t = r P , J⊆ [k], |J| = t, v ∈ Z t q (10)
Functions in I t q are known to bring inapproximability bounds for k CSP-q. Notably, for all k ≥ 3, if the accepting entries of a k-ary predicate P ∈ I 2 q form a subgroup of Z k q , then Max CSP-P is NP-hard to approximate within any constant standard factor greater than r P [START_REF] Chan | Approximation resistance from pairwise-independent subgroups[END_REF]. For instance, the predicate that accepts solutions to equation y 1 + y 2y 3 ≡ 0 mod q over Z 3 q is such a predicate. Thus assume that P i ∈ I t q , i ∈ [m] holds for some t > 0. When this occurs, it is possible to fix up to t coordinates of π V (M r ) Ji , and still obtain when averaging

P i (x Ji + π V (M r ) Ji ) over r ∈ [R] the average value of P i . Hence, rather than a strong coloring {U 1 , . . . , U ν } of G I , we consider partition V = {U 1 , . . . , U ν-t , V 0 } where V 0 = U ν-t+1 ∪ . . .∪ U ν of [n]. Array M consequently has ν -t + 1 columns. Given i ∈ [m],
we denote by K i the set {c i,1 , . . . , c i,ki } ∩ {1, . . . , ν -t} of column indices, by s i it cardinality. For the sake of clarity, we assume w.l.o.g. that K i = {c i,1 , . . . , c i,s }. Over S(I, x), P i is evaluated at entries

(x i1 + M ci,1 r , . . . , x is i + M ci,s i r , x is i +1 + M ν-t+1 r , . . . , x i k i + M ν-t+1 r ), r ∈ [R]
where k i -s i ≤ t and s i ≤ min{ν -t, k i } ≤ min{ν -t, k}. We deduce that setting e.g. M = N × {0} where N is an orthogonal array of strength min{νt, k} on νt columns, one obtains a pair (V, M) that satisfies [START_REF] Hedayat | Orthogonal Arrays: Theory and Applications[END_REF].

Thereafter, given an instance I of CSP-q, we denote by ν I the strong chromatic number of G I (that is, ν I is the smallest integer such that I is ν I -partite), and by t I the greatest integer such that P i ∈ I tI q , i ∈ [m] (thus t I possibly is 0). In all, the preceding discussion establishes the following connection between the average solution value on CSP instances and orthogonal arrays: Theorem 1. Given any three integers q ≥ 2, t ≥ 1 and ν ≥ t, we define ρ(ν, q, t) as the greatest ρ ∈ [0, 1] for which an OA(R, ν, q, t) with highest frequency ρ exists. (For example, the OA(27, 5, 3, 2) of Table 2 does achieve ρ(5, 3, 2) = 2/27.)

Then for all integers k ≥ 2, q ≥ 2, the average solution value on an instance I of k CSP-q is ρ(ν It I , q, min{k, ν It I })-approximate.

Approximation Quality of the Average Solution Value

From an Alphabet Size to a Greater One

We derive lower bounds for ρ E from orthognonal arrays with a relatively small number of rows of the literature. Such arrays often require q to be a prime power. However, we can derive lower bounds for ρ E in case when q is not a prime power by reduction to the case when q is a prime power: Theorem 2. Let q ≥ 3, k ≥ 2 be two integers. Then for all primes p, the average solution value on an instance I of k CSP-q is ρ(ν I , p log p q , k)-approximate.

Proof. Let κ = log p q , d = p κ , and let π = (π 1 , . . . , π n ) be a vector of surjective maps from Z d to Z q . We interpret I as the instance f π (I) of CSP-d where:

1. for each j ∈ [n], there is in f π (I) a variable z j with domain Z d ; 2. for each i ∈ [m], there is in f π (I) a constraint P i (π i1 (z i1 ), . . . , π i k i (z i k i )), with the same associated weight w i as C i in I.

So as to retrieve solutions of I from solutions of f π (I), we define g π (I, .) by g π (I, z) = (π 1 (z 1 ), . . . , π n (z n )), z ∈ Z n d . By construction, g π (I, .) is surjective, and satisfies for all z ∈ Z n d that v(I, g π (I, z)) = v(f π (I), z). The extremal solution values on I and f π (I) therefore satisfy: opt(f π (I)) = opt(I), wor(f π (I)) = wor(I) [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF] By contrast, E Z [v(f π (I), Z)] may differ from E X [v(I, X)], due to the fact that two distinct vectors x, x ∈ Z n q may be the image by g π (I, .) of a distinct number of vectors of Z n d . Hence, rather than a single vector π, we consider a vector Π = (Π 1 , . . . , Π n ) of random maps that are independently and uniformly distributed over the set M of surjective maps from

Z d to Z q . Let j ∈ [n], a ∈ Z d , b ∈ Z q , b ∈ Z q \{b}.
Consider then function σ on M that maps any π ∈ M to the map σ(π) :

Z d → Z q defined by σ(π)(c) = b if π(c) = b, b if π(c) = b ,
and π(c) otherwise. σ clearly is a bijection on M. Hence, we have:

|{π ∈ M | π(a) = b}| = |{π ∈ M | σ(π)(a) = b }| = |{π ∈ M | π(a) = b }| Since q-1 b=0 P Πj [Π j (a) = b] = 1 holds for all j ∈ [n]
and all a ∈ Z d , we first deduce that probabilities P Πj [Π j (a) = b] all are equal to 1/q. We then deduce that probabilities P

Π [g Π (I, z) = x], z ∈ Z n d , x ∈ Z n q all are equal to n j=1 P Πj [Π j (z j ) = x j ] = 1/q n .
Accordingly, given any z ∈ Z n d , we have:

E Π [v(I, g Π (I, z))] = x∈Z n q v(I, x) × P Π [g Π (I, z) = x] = E X [v(I, X)]
We eventually deduce that the expected average solution value on f Π (I) satisfies:

E Π [E Z [v(f Π (I), Z)]] = E Z [E Π [v(I, g Π (I, Z))]] = E X [v(I, X)] (12)
By ( 12), there exists [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF], for such a vector π * , we have ρ E (I) ≥ ρ E (f π * (I)). Since the supports of the constraints are unchanged by f π , π ∈ M n , the result follows from Theorem 1.

π * ∈ M n such that E Z [v(f π * (I), Z)] ≤ E X [v(I, X)] while by

Deriving Bounds from Orthogonal Arrays of the Litterature

Let q ≥ 2, t ≥ 1 and ν ≥ t be three integers. The smallest integer R such that an OA(R, ν, q, t) exists is referred to as F (ν, q, t) in the literature. The highest frequency of a word in an array that achieves F (ν, q, t) naturally is at least 1/F (ν, q, t). Also observe that F (ν, q, k) ≤ F (ν , q, k) naturally holds for all integers ν > ν. Hence, according to Theorems 1 and 2, given any instance I of k CSP-q, we may exhibit lower bounds for ρ E (I) using inequalities:

ρ E (I) ≥ 1/F (ν , q, min{ν I -t I , k}), ν ∈ N, ν ≥ ν I -t I (13) ρ E (I) ≥ 1/F (ν , p log p q , k), ν , p ∈ N, ν ≥ ν I , p prime (14)
First, we consider the case of instances with a bounded strong chromatic number. Given three integers q ≥ 2, k ≥ 1, ν ≥ k, there exists an OA(q k , ν, q, k) provided that one of the following cases occurs (see e.g. [START_REF] Hedayat | Orthogonal Arrays: Theory and Applications[END_REF]):

1. ν ∈ {k, k + 1}; 2. q is a prime power, q > k and ν ∈ {k + 2, . . . , q + 1}; 3. k = 3, q is a power of 2, q > 3 and ν = q + 2.

is trivial, considering

M Z k q if ν = k, M {y ∈ Z k+1 q
| y 1 + . . . + y k+1 ≡ 0 mod q} otherwise. 2. and 3. are due to Bush. We deduce from ( 13) and ( 14) the following lower bounds for ρ E in O(max{q, k})-partite instances of k CSP-q: Corollary 1. Let q ≥ 2, k ≥ 2, ν ≥ k be three integers with ν ∈ O(max{q, k}) and I be a ν-partite instance of k CSP-q. We denote by p κ the smallest prime power greater than or equal to q. Then on I, ρ E (I) is bounded below by:

1. 1/q ν-tI > 1/q k if ν < k + t I ; 2. 1/q k if ν ≤ k + t I + 1; 3. 1/q k if
q is a prime power, q > k and ν ≤ q + t I + 1; 4. 1/p κk ≥ 1/(2(q -1)) k if q is not a prime power, p κ > k and ν ≤ p κ + 1; 5. 1/q 3 if k = 3, q is a power of 2, q > 3 and ν ≤ q + t I + 2; 6. 1/2 3 log 2 q ≥ 1/(2(q -1)) 3 if k = 3, q is not a power of 2 and ν ≤ 2 log 2 q +2. For example, on a k-partite instance I of Lin-q in which equations all are of the form (x i1 + . . . + x i k ≡ α i,0 mod q), we have ρ E (I) ≥ 1/q. For greater integers ν, we refer to families of orthogonal arrays that originate from infinite families of linear codes. Over the boolean alphabet, we consider dual codes of BCH codes. Namely, binary BCH codes allow for all integers κ ≥ 3, k ≥ 1 such that 2 κ -1 ≥ 2k + 1 to construct an OA(R, 2 κ -1, 2, 2k) with R ≤ 2 κk (see e.g. [START_REF] Hedayat | Orthogonal Arrays: Theory and Applications[END_REF][START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]). For such pairs (κ, k), we consequently have

F (2 κ -1, 2, 2k) ≤ 2 κk . Besides, as reported in [8], F (2 κ , 2, 2k + 1) = 2 × F (2 κ -1, 2, 2k
). Hence, it also holds for such pairs (κ, k) that F (2 κ , 2, 2k + 1) ≤ 2 1+κk . Accordingly:

Corollary 2. Let k ≥ 2 be an integer. Then on all instances I of k CSP with ν I -t I ≥ k + 2, ρ E (I) is bounded below by: 1. 1/2 log 2 (νI -tI +1) k/2 ≥ 1/2 k/2 × 1/(ν I -t I ) k/2 if k is even; 2. 1/2 1+ log 2 (νI -tI ) k/2 ≥ 1/2 1+ k/2 × 1/(ν I -t I -1) k/2 if k is odd.
For E2 Lin-2, which is a special case of 2 CSP(I 1

2 ), we thus obtain for ρ E a lower bound of 1/2 log 2 νI . And this is a tight bound: given n ∈ N * , let I n refer to the instance where G In is the complete graph K 2n , and equations all are of the form (x j + x h ≡ 0 mod 2). I n is trivially satisfiable by the vectors of allzeros and of allones, and v(I n , .) is minimized at balanced vectors. Hence, we have:

ρ E (I n ) = ( 2n 2 /2 -2 n 2 )/( 2n 2 -2 n 2 ) = 1/(2n) = 1/ν
In , n ∈ N * For greater prime powers q, trace-codes of Reed-Solomon codes give rise for all integers s, k, λ such that q s ≥ k > q λ ≥ 1 to q 1+s(k-1-λ) × q s orthogonal arrays of strength k on Z q [START_REF] Bierbrauer | Construction of orthogonal arrays[END_REF]. Accordingly: Corollary 3. Let q ≥ 3, k ≥ 2 be two integers. We denote by p κ the smallest prime power such that p κ ≥ q, by λ the greatest integer such that k > p κλ . If q is a prime power, then for all instances I of k CSP-q with ν It I ≥ k, we have:

ρ E (I) ≥ 1/q 1+ log q (νI -tI ) (k-1-λ) ≥ 1/q k-λ × 1/(ν I -t I -1) k-1-λ
Otherwise, for all instances I of k CSP-q with ν I ≥ k, we have:

ρ E (I) ≥ 1/p κ(1+ log p κ νI (k-1-λ)) ≥ 1/(2(q -1)) k-λ × 1/(ν I -1) k-1-λ

Concluding Remarks

In order to evaluate the quality of the average solution value, one shall compare the lower bounds we obtain for ρ E to both gain and differential approximability bounds of the literature. The differential approximation measure (see [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF] for an introduction) evaluates the performance of a given solution x by the ratio ρ D (I, x) = v(I, x)wor(I) opt(I)wor(I) [START_REF] Khot | Linear equations modulo 2 and the $L 1$ diameter of convex bodies[END_REF] Thus ρ E (I) precisely is the average differential ratio on I. ρ-differential approximable problems are defined just as the same as for the gain approximation measure. Notice that by definition of ρ G (I, x), ρ E (I) and ρ D (I, x), we have:

ρ D (I, x) = ρ E (I) + (1 -ρ E (I)) × ρ G (I, x) (16)
Hence, if a given CSP Π is ρ-gain approximable, and the average solution value is δ-approximate for Π, then Π is [ρ + δ(1ρ)]-differential approximable. We summarize in Table 3 the bounds we are aware of. In this table, we take into account the fact that gain approximability lower bounds that hold for Lin-2 somehow extend to k CSP-q for all integers q ≥ 2, k ≥ 3: Proposition 1. For all integers q ≥ 2, k ≥ 2, if (k log 2 q )Lin-2 is approximable within gain factor ρ, then k CSP-q is approximable within differential factor ρ and, provided that q is a power of 2, within gain factor ρ. Table 3. Differential (ρD) and gain (ρG) approximability bounds for k CSP-q that are achievable by either deterministic (det.) or randomized (exp.) algorithms, and their comparison to ρE: p κ refers to the smallest prime power ≥ q; inapproximability bounds are given for all constant ε > 0, and assume P = NP.

Approximability bounds in k-partite instances of

Ek CSP-q k q t I ρG det. ρD det. ρE 0.561 [1] 0.78 [1] = 1/2 ≥ 3 ≥ = 2 = 2 = 1 2 =k -1 ¬ ε [4] ¬ 1/q + ε [4] ≥ 1/q ≥ 3 ≥ 2, ≤ k = 2 ¬ ε [4] ¬ O(k/q k-1 ) + ε [4] ≥ 1/q k-2 ≥ 3 ≥ k = 2 ¬ ε [4] ¬ O(k/q k-2 ) + ε [4] ≥ 1/q k-2
Gain approximability bounds for Ek CSP-q

k q t I ρG det. ρG exp. ρE = 2 = 2 ≥ 0 Ω(1/ ln n) [16] Ω(1/νI ) = 3 = 2 = 2 Ω(1/m) [11] Ω( ln n/n) [14] = 1/2 ≥ 4 = 2 ≥ 0 Ω(1/m) [11] Ω(1/ √ m) [11] Ω(1/ν k/2 I ) ≥ 2 = 2 κ , ≥ 4 ≥ 0 Ω(1/m) Ω(1/ √ m) Ω(1/ν k-1-log 2 κ (k-1) I )
Other differential approximability bounds for k CSP-q k, q ρD det. ρD exp. ρE k = 2 or (k, q) = (3, 2) Ω(1) [START_REF] Culus | 2 CSPs all are approximable within some constant differential factor[END_REF][START_REF] Escoffier | Differential approximation of MIN SAT, MAX SAT and related problems[END_REF] Ω(1/νI )

k ≥ 3 and q ≥ 3 Ω(1/m) Ω(1/ √ m) Ω(1/ν k-1-log p κ (k-1) I )
Author Proof

Proof (sketch). Let I be an instance of k CSP-q. First map I to an instance J of (κk)CSP-2 where κ = log 2 q using a binary encoding of the variables. Then map J to an instance H of (κk)Lin-2 using the discrete Fourier transform. When q = 2 κ , the average solution values on I and J (and thus, on H) are identical.

For such symptomatic CSPs as the restriction of CSP(I k-1 q ) to k-partite instances for all k ≥ 3, and CSP(O q ), E X [v(I, X)] trivially brings the same differential approximation guarantee of 1/q, which essentially is optimal, as in the standard approximation framework. By contrast, for 2 CSP-2, E X [v(I, X)] is of rather low quality, considering that Ω(1/n) is a tight lower bound for ρ E (I), while 2 CSP-2 is approximable within gain and differential factor respectively Ω(1/ ln n) and Ω [START_REF] Garey | Some simplified NP-complete graph problems[END_REF]. For greater integers k, in dense instances of k CSP-2, the factor of Ω(1/n k/2 ) E X [v(I, X)] gains over wor(I) is significantly greater than the best gain approximation guarantee of Ω(1/m) known so far, and comparable to the best expected gain factor of Ω(1/ √ m) known so far. Starting with an R×ν-array M on Z q , we can define a probability distribution on Z ν q by associating with each vector u ∈ Z ν q its frequency in M . Then, M is orthogonal of strength t iff this distribution is balanced t-wise independent. A function P : Z ν q → R with minimal value P * similarly belongs to I t q iff 1/q ν × (P -P * )/(r P -P * ) defines a balanced t-wise independent distribution on Z ν q . This classical notion is strongly involved in the exhibition of approximation resistant predicates (notably see [START_REF] Chan | Approximation resistance from pairwise-independent subgroups[END_REF][START_REF] Austrin | Randomly supported independence and resistance[END_REF]). The analysis we proposed therefore reinforces the connection between balanced t-wise independence and approximability of k CSP-q by allowing the establishment of positive results. Observe that the arrays we used contain no duplicated rows. Therefore, lower bounds for ρ E in νpartite instances could be improved by exhibiting orthogonal arrays (or balanced k-wise independent measures) that maximize their highest frequency, especially in case when ν ∈ Θ(max{q, k}). Table 4 provides a few illustrations of this fact.

The average differential ratio has potential to provide new insights into CSPs. First, the method we used to obtain lower bounds for ρ E not only shows that E X [v(I, X)] achieves some differential ratio ρ, but also indicates that ρdifferential approximate solutions are spread all over the solution set. It thus provides additional information on the repartition of solution values. Although we took into account parameters ν I and t I so as to refine our analysis, apart from the arity of their constraints, we did not restrict the instances we considered. Hence, a next step should be the identification of hypergraphs and function properties that allow to build partition-based solution multisets of low cardinality that satisfy [START_REF] Hedayat | Orthogonal Arrays: Theory and Applications[END_REF]. More generally, it would be worthwhile to characterize such functions families F as the set of submodular functions for which Max CSP(F) or Min CSP(F) admits a constant lower bound for ρ E . Finally, the properties of ρ E viewed as a complexity measure, including its connections to other measures, should be investigated. Notably, because for E3 Lin-2, ρ E ∈ O(1), the authors of [START_REF] Escoffier | Differential approximation of MIN SAT, MAX SAT and related problems[END_REF] could derive from the hardness result of [START_REF] Håstad | Some optimal inapproximability results[END_REF] as regards E3 Lin-2 a constant inapproximability bound of 0 for the diameter of 3 Sat instances.

Table 4. Comparison of arrays that maximize their highest frequency among those that achieve F (ν, q, k) (on the right) to arrays that minimize their number of rows among those that achieve ρ(ν, q, k) (on the left). In both cases, we indicate the ratio R * /R of the highest number of occurrences of a word to the number of rows in the array. (These arrays were calculated by computer using linear programs.)

ν

Fig. 1 .

 1 Fig. 1. Quantities involved in ρG(I, x) and ρE(I).

Author Queries

Chapter 31 Query Refs.

Details Required

Author's response AQ1 This is to inform you that corresponding author has been identified as per the information available in the Copyright form.

AQ2

Per Springer style, both city and country names must be present in the affiliations. Accordingly, we have inserted the city names in affiliations. Please check and confirm if the inserted city names are correct. If not, please provide us with the correct city names.

AQ3

References [13, 14, 15, 16 and 17] are given in the list but not cited in the text. Please cite them in text or delete them from the list.