Manu Basavaraju
email: manub@imsc.res.in

Acyclic Chromatic Index of Fully Subdivided Graphs and Halin Graphs

Keywords: Acyclic edge coloring, acyclic edge chromatic number, subdivided graphs, Halin graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a (G). A graph G is called fully subdivided if it is obtained from another graph H by replacing every edge by a path of length at least two. Fully subdivided graphs are known to be acyclically edge colorable using ∆ + 1 colors since they are properly contained in 2-degenerate graphs which are acyclically edge colorable using ∆ + 1 colors. Muthu, Narayanan and Subramanian gave a simple direct proof of this fact for the fully subdivided graphs. Fiamcik has shown that if we subdivide every edge in a cubic graph with at most two exceptions to get a graph G, then a (G) = 3. In this paper we generalise the bound to ∆ for all fully subdivided graphs improving the result of Muthu et al. In particular, we prove that if G is a fully subdivided graph and

where T is a rooted tree on the vertex set V and C is a simple cycle on the leaves of T . Such a graph G is called a Halin graph if G has a planar embedding and T has no vertices of degree 2. Let Kn denote a complete graph on n vertices. Let G be a Halin graph with maximum degree ∆. We prove that,

Introduction

All graphs considered in this paper are finite and simple. A proper edge coloring of G = (V, E) is a map c : E → C (where C is the set of available colors ) with c(e) = c(f ) for any adjacent edges e,f . The minimum number of colors needed to properly color the edges of G is called the chromatic index of G and is denoted by χ (G). A proper edge coloring c is called acyclic if there are no bichromatic cycles in the graph. In other words an edge coloring is acyclic if the union of any two color classes induces a set of paths (i.e., linear forest) in G. The acyclic edge chromatic number (also called acyclic chromatic index), denoted by a (G), is the minimum number of colors required to acyclically edge color G. The concept of acyclic coloring of a graph was introduced by Grünbaum [START_REF] Grünbaum | Acyclic colorings of planar graphs[END_REF]. The acyclic chromatic index and its vertex analogue can be used to bound other parameters like oriented chromatic number and star chromatic number of a graph, both of which have many practical applications, for example, in wavelength routing in optical networks ( [START_REF] Amar | All to all wavelength routing in all-optical compounded networks[END_REF], [START_REF] Kostochka | Acyclic and oriented chromatic numbers of graphs[END_REF] ). Let ∆ = ∆(G) denote the maximum degree of a vertex in graph G. By Vizing's theorem, we have ∆ ≤ χ (G) ≤ ∆ + 1 (see [START_REF] Diestel | Graph Theory[END_REF] for proof). Since any acyclic edge coloring is also proper, we have a (G) ≥ χ (G) ≥ ∆.

It has been conjectured by Alon, Sudakov and Zaks [START_REF] Alon | Acyclic edge-colorings of graphs[END_REF] (and much earlier by Fiamcik [START_REF] Fiamcik | The acyclic chromatic class of a graph[END_REF]) that a (G) ≤ ∆ + 2 for any G. The best known result up to now for arbitrary graph, is by Ndreca et al. [START_REF] Ndreca | Improved bounds on coloring of graphs[END_REF], who showed that a (G) ≤ 9.62∆.

Though the best known upper bound for general case is far from the conjectured ∆ + 2, the conjecture has been shown to be true for some special classes of graphs. Alon, Sudakov and Zaks [START_REF] Alon | Acyclic edge-colorings of graphs[END_REF] proved that there exists a constant k such that a (G) ≤ ∆+2 for any graph G whose girth is at least k∆ log ∆. Muthu, Narayanan and Subramanian proved the conjecture for grid-like graphs [START_REF] Muthu | Optimal acyclic edge coloring of grid like graphs[END_REF]. In fact they gave a better bound of ∆ + 1 for these class of graphs. It has also been shown by Alon and Zaks [START_REF] Alon | Algorithmic aspects of acyclic edge colorings[END_REF] that determining whether a (G) ≤ 3 is NP-complete for an arbitrary graph G.

Our results: subdivided graphs

A graph G is called fully subdivided if it is obtained from another graph H by replacing every edge by a path of length at least two. Fully subdivided graphs are known to be acyclically edge colorable using ∆+1 colors since they are properly contained in 2-degenerate graphs which are acyclically edge colorable using ∆ + 1 colors [START_REF] Basavaraju | Acyclic edge coloring of 2-degenerate graphs[END_REF]. Muthu, Narayanan and Subramanian [START_REF] Muthu | Some graph classes satisfying acyclic edge colouring conjecture[END_REF] gave a simple direct proof of this fact for the fully subdivided graphs. Fiamcik [START_REF] Fiamcik | Acyclic chromatic index of a subdivided graph[END_REF] has shown that if we subdivide every edge in a cubic graph with at most two exceptions to get a graph G, then a (G) = 3. In this paper we generalise the bound to ∆ for all fully subdivided graphs improving the result of [START_REF] Muthu | Some graph classes satisfying acyclic edge colouring conjecture[END_REF]. Note that the condition ∆ ≥ 3 is necessary in all statements in Theorem 1 and Corollaries 1 and 2 below because a cycle is a subdivided graph with ∆ = 2 and it requires 3 = ∆ + 1 colors.

First we prove the bound for a class of bipartite graphs and then obtain the result for fully subdivided graphs. Let deg G (x) denote the degree of the vertex x in graph G. We will abbreviate the notation to deg(x) when the graph G is understood from the context.

Theorem 1 Let G = (V, E) be a bipartite graph with maximum degree ∆ ≥ 3, and let V = A ∪ B be such that for any a ∈ A, deg(a) = 2. Then a (G) = ∆.

Noting that fully subdivided graphs are a sub class of the bipartite graphs defined in Theorem 1, the following Corollary is obvious:

Corollary 1 Let G be a fully subdivided graph of some graph H, where every edge is replaced by a path of length exactly two and ∆(G) ≥ 3. Then a (G) = ∆(G).

Remark Note that though graphs referred in the statement of Theorem 1 and Corollary 1 look the same, they are in fact different. Though a fully subdivided graph is a bipartite graph as defined in Theorem 1, it cannot have any cycle of length 4. Any cycle in a fully subdivided graph will be of length at least 6. But the bipartite graph we have considered in Theorem 1 can have cycles of length 4.

Corollary 2 Let G be a fully subdivided graph of some graph H, where every edge is replaced by a path of length at least two and ∆(G) ≥ 3. Then a (G) = ∆(G).

Proof: Suppose every edge of H is replaced by a path of exactly two edges to get a graph G. Then by Corollary 1, we have a (G) = ∆. Thus there exists an edge uv in H which is replaced in G by a path of length at least three. Now let that path be (u = a 0 , a 1 , a 2 , . . . , a k , a k+1 = v). Now we contract the edge a 1 a 2 to a 1 to get a graph G . Graph G is again a subdivided graph and by induction has an acyclic edge coloring using ∆ colors. Let c be such a coloring of G . Now we obtain a coloring c of G from G as follows: Let c (a 0 a 1 ) = α, c (a 1 a 3 ) = β. Let γ be a color different from α and β. Now let c(a 2 a 3 ) = β and c(a 1 a 2 ) = γ and c(e) = c (e) for any other edge e of G. It is easy to see that the modified coloring is acyclic. It is proper since c is proper and c(a 0 a 1 ), c(a 1 a 2 ), c(a 2 a 3 ) are all distinct. It is acyclic because if there is a bichromatic cycle created due to the recoloring, then it has to contain the edges a 0 a 1 , a 1 a 2 , a 2 a 3 . But we already know that all these three edges are colored differently. Thus c is acyclic.

2

Our results: Halin Graphs

Consider a graph G = (V, E), with E = E(T ) ∪ E(C)
where T is a rooted tree on the vertex set V and C is a simple cycle on the leaves of T . Such a graph G is called a Halin graph if G has a planar embedding and T has no vertices of degree = 2. The notion of Halin graphs was first used by Halin [START_REF] Halin | Studies on minimally n-connected graphs[END_REF] in his study of minimally 3-connected graphs. Let K n denote the complete graph on n vertices. In this paper, we prove the following theorem, Theorem 2 Let G be a Halin graph with maximum degree ∆. Then,

a (G) =    ∆ + 2 = 5 if G is K 4 ∆ + 1 = 4 if ∆ = 3 and G is not K 4 ∆ otherwise.

Preliminaries

Let G = (V, E) be a simple, finite and connected graph of n vertices and m edges. Let x ∈ V . Then N G (x) will denote the neighbours of x in G. We abbreviate the notation to N (x) when the graph G is understood from the context. Let c : E → {0, 1, . . . , k -1} be an acyclic edge coloring of G. For an edge e ∈ E, c(e) will denote the color given to e with respect to the coloring c. For x, y ∈ V , when e = xy we may use c(xy) instead of c(e). For S ⊆ V , we denote the induced subgraph on S by G[S].

We denote the set of colors in a coloring c by C. Let c be a partial coloring of G which uses at most |C| colors. For any vertex u ∈ V (G), we define F u (c) = {c(e)|e = uv ∈ E(G)}. For an edge ab ∈ E, we define S ab (c) = F b -{c(ab)}. Note that S ab (c) and S ba (c) can be different. We will abbreviate the notation to F u and S ab when the coloring c is understood from the context.

Maximal bichromatic Path: Consider the subgraph induced by any two colors α and β with respect to any proper coloring c. The (α, β)-subgraph consists of even cycles, bichromatic paths of length at least two, isolated edges and isolated vertices. Now when we say maximal bichromatic path, we only concentrate on bichromatic paths of length at least two, ignoring the even bichromatic cycles, isolated edges and isolated vertices. Thus an (α,β) maximal bichromatic path with respect to a proper coloring c of G is a path-component of the (α, β)-subgraph that consists of at least two edges. An (α,β,a,b) maximal bichromatic path is an (α,β) maximal bichromatic path which starts at the vertex a with an edge colored α and ends at b. We emphasise that the edge of the (α,β,a,b) maximal bichromatic path incident on vertex a is colored α and the edge incident on vertex b can be colored either α or β. Thus the notations (α,β,a,b) and (α,β,b,a) have different meanings. Also note that any maximal bichromatic path will have at least two edges. The following fact is obvious from the definition of acyclic edge coloring: Fact 1 ( [START_REF] Basavaraju | Acyclic edge coloring of 2-degenerate graphs[END_REF]) Given a pair of colors α and β of a proper coloring c of G, there can be at most one (α,β) maximal bichromatic path containing a particular vertex v, with respect to c.

A color α = c(e) is a candidate for an edge e in G with respect to a partial coloring c of G if none of the adjacent edges of e are colored α. A candidate color α is valid for an edge e if assigning the color α to e does not create any bichromatic cycle in G.

Critical Path: Let ab ∈ E and c be a partial coloring of G. Then a (α, β,a,b) maximal bichromatic path which starts out from the vertex a via an edge colored α and ends at the vertex b via an edge colored α is called an (α, β, ab) critical path. Note that any critical path will be of odd length. Moreover the smallest length possible is three. Color Exchange: Let c be a partial coloring of G. Let u, i, j ∈ V (G) and ui, uj ∈ E(G). We define Color Exchange with respect to the edge ui and uj, as the modification of the current partial coloring c by exchanging the colors of the edges ui and uj to get a partial coloring c , i.e., c (ui) = c(uj), c (uj) = c(ui) and c (e) = c(e) for all other edges e in G. The color exchange with respect to the edges ui and uj is said to be proper if the coloring obtained after the exchange is proper. The color exchange with respect to the edges ui and uj is valid if and only if the coloring obtained after the exchange is acyclic.

Lemma 1 ([4]

) Let u, i, j, a, b ∈ V (G), ui, uj, ab ∈ E. Also let {λ, ξ} ∈ C such that {λ, ξ} ∩ {c(ui), c(uj)} = ∅ and {i, j} ∩ {a, b} = ∅. Suppose there exists an (λ,ξ,ab)-critical path that contains vertex u, with respect to a valid partial coloring c of G. Let c be the partial coloring obtained from c by the color exchange with respect to the edges ui and uj. If c is proper, then there will not be any (λ,ξ,ab)-critical path in G with respect to the partial coloring c .

Proof of Theorem 1

Let G be a minimum counterexample (with respect to the number of edges) for the theorem statement. It is easy to see that G is 2-connected since otherwise, the acyclic edge coloring of the blocks of G could be easily extended to G.

The graph G = (V, E) is a bipartite graph with bipartition A, B and for any a ∈ A, deg(a) = 2. Let a 1 ∈ A. Let C be the set of colors. We have |C| = ∆(G). Now since G is a minimum counterexample, G -{a 1 } is acyclically edge colorable using at most ∆ colors and let c be such a coloring of G -{a 1 }. Let N (a 1 ) = {x, b 1 }. Now we try to extend the coloring c to a valid coloring c of G. Now C -F b1 is the set of candidate colors for the edge b 1 a 1 . Assign a color from C -F b1 to the edge b 1 a 1 to get a coloring c . Without loss of generality, we assume that c (b

1 a 1 ) = 1. Let N (x) = {a 1 , a 2 , . . . , a k }, where k = deg(x) and N (a i ) = {x, b i }. Suppose deg(x) < ∆. Then if c (b 1 a 1 ) / ∈ F x ,
there exists a candidate color for the edge xa 1 . It is also valid since if there is a bichromatic cycle created due to this coloring then it has to pass through the vertex x, implying that c (b 1 a 1 ) ∈ F x , a contraction to our assumption. On the other hand if c (b 1 a 1 ) ∈ F x , then there are at least two candidate colors for the edge xa 1 , say α and β. If both of them are not valid then by Fact 2 there exist (1, α, xa 1 ) and (1, β, xa 1 ) critical paths with respect to c . Since c (b 1 a 1 ) ∈ F x , without loss of generality let c (xa 2 ) = 1. Then the above mentioned critical paths have to pass through a 2 , implying that 1, α, β ⊆ F a2 , a contradiction since deg(a 2 ) = 2. Thus at least one of α or β is valid for the edge xa 1 .

Thus deg(x) = ∆. Now we have the following cases: Recolor xa j using color β to get a valid coloring d and we are in case 1.

2.2: c (a i b i ) = 1 for all i, 2 ≤ i ≤ k.
Without loss of generality we can assume that c (xa 2 ) = 2. Now recolor edge xa 1 using color 2, edge xa 2 using color 1 and discard the color of edge a 2 b 2 to get a coloring d. Now again this situation is similar to assigning color to edge xa 1 , here b 2 and a 2 taking the role of x and a 1 respectively. The vicinity of b 2 will be similar to x. Thus we are again in the same cases as in the case of x. Either we can extend the coloring as in the cases described above or we are in the case where

1 / ∈ F b2 (d), for y i ∈ N G (b 2 ), 1 ∈ F yi (d) and {d(xa 2 ) = 1} ∪ F b2 (d) = C. Hence 2 ∈ F b2 (d).
We move on like this along the (1, 2)bichromatic path that was in the coloring c by iterating the previous recoloring procedure. Since c was acyclic we cannot come back to a vertex which we had already visited before. We now want to prove the existence of a vertex z ∈ B such that for some vertex w i ∈ N (z), 1 / ∈ F wi (d) and so we can extend the coloring to the whole graph G using subcase 21. Suppose by contradiction we visited all vertices of B and come back to x via b 1 , we know that with respect to c , c (a 1 b 1 ) = 1 and c (xa 2 ) = 2. This means that there exists a (1, 2, a 1 , x) bichromatic path which is of even length. This path along with the edge xa 1 , will give an odd cycle, a contradiction since G is bipartite. We can infer that there exists a vertex z such that 1 / ∈ F wi (d), for some w i ∈ N (z). Now we are in subcase 21. Thus we have a coloring for G using ∆ colors and hence a contradiction to our assumption that G is the minimum counterexample.

Proof of Theorem 2

Let G = (V, E) be a simple, finite and connected Halin graph of n vertices and m edges. For a rooted tree T , the depth of the root is taken to be 0 and the depth of any other vertex is one greater than the depth of its parent. The depth of the tree is taken to be the maximum depth of a vertex in it. If a Halin graph has an acyclic edge coloring using exactly the number of colors specified in Theorem 2, then the graph is said to have a desired coloring.

Note that there is a planar embedding for the Halin graph. For the proof we choose a maximum degree vertex of T to be the root. This ensures that the root is not a leaf. The cycle C is passing through the leaves of the tree T . Let σ be a circular ordering of the leaves of T , obtained as we traverse the cycle C in the clockwise direction.

Claim 1 Halin graph of depth 1 has a desired coloring.

Proof: Let G be a Halin graph on n vertices. Let u be the root. If G = K 4 , we know that H is acyclically edge colorable using 5 colors. Since G = K 4 , clearly ∆(G) ≥ 4. Let a 0 , a 1 , . . . , a ∆-1 be the children of u ordered with respect to the circular ordering σ. We color the graph G as follows:

• c(u, a i ) = i for 0 ≤ i ≤ ∆ -1. • ∀i, 0 ≤ i ≤ ∆ -1, c(a i a i+1 (mod ∆) ) = c(ua i+2 (mod ∆) ).
It is easy to check that the coloring is proper and acyclic.

2

Let u be an internal vertex of T with maximum depth. In view of Claim 1, we can assume that the depth of T is more than 1 and thus u is not the root. Let v be the parent of u. Since u is an internal vertex of T with maximum depth it is easy to see that the children of u have to be consecutive with respect to the circular ordering σ (Recall the way the ordering was defined). Let a 0 , a 1 , . . . , a k-1 , 2 ≤ k ≤ ∆ -1 be the children of u ordered with respect to the circular ordering σ. Let x be the predecessor of a 0 and y be the successor of a k-1 with respect to the ordering σ. That is N G (a 0 ) = {x, a 1 , u} and N G (a k-1 ) = {y, a k-2 , u}. It is easy to see that since u is not the root there are at least 2 more leaves in T, in addition to a 0 , a 1 , . . . , a k-1 . Therefore x = y.

We prove Theorem 2 by induction on the number of vertices. Let G be a Halin graph on n vertices. Now we get a Halin graph G by contracting the subset {u, a 0 , a 1 , . . . , a k-1 } of V . Note that since the vertex with maximum degree of G was chosen as the root and depth of T is more than 1, we have ∆(G ) = ∆(G) = ∆. Let z be the vertex resulting from this contraction. Then it is easy to see that N G (z) = {v, x, y}. Now by induction hypothesis G has a desired coloring. We consider two cases:

case 1: G = K 4 .
Here we have ∆ = 3. In this case it is easy to verify that G has to be isomorphic to the graph given in Figure 1. Thus it is sufficient to show that this graph can be acyclically edge colored using 4 colors. The coloring is explicitly given in Figure 1.

case 2: G = K 4 .
Note that in G the edges zv, zx and zy are mutually adjacent and hence the colors on them have to be different. We can also assume that the colors on the edges zv, zx, zy are ∆-1, 0, 1 respectively since otherwise we can rename the colors as required.

We get the coloring d of G from c of G as follows:

• d(xa 0 ) = c(xz) = 0, d(a k-1 y) = c(zy) = 1. • d(ua 0 ) = 1, d(ua 1 ) = 0 and d(ua i ) = i for 2 ≤ i ≤ k -1 ≤ ∆ -2. • ∀i, 0 ≤ i ≤ k -3, d(a i a i+1 ) = d(ua i+2 ).
• d(a k-2 a k-1 ) = c(zv) = ∆ -1.

• d(uv) = c(zv) = ∆ -1.

• d(e) = c(e) for all other edges e.

Claim 2

The coloring d is acyclic.

Proof: It is clear that the coloring is proper. We claim that this coloring is acyclic also. First observe that there cannot be a bichromatic cycle that contains any one of the edges uv, xa 0 or ya k-1 . This is because if there is a bichromatic cycle containing any one of these edges then it has to contain at least two edges from the three mentioned. This implies that the bichromatic cycle existed even in G since these edges were present in G too as zv, zx and zy with the same colors (Recall that x, y, v are distinct vertices in G ).

Thus we can infer that if there is a bichromatic cycle then it has to be formed in the subgraph induced by the vertices u, a 0 , a 1 , . . . a k-1 . Now with respect to this induced subgraph each color class has at most two edges and thus if there is a bichromatic cycle, it has to be a 4-cycle. In this induced subgraph the color classes 0, 1 and ∆ -1 have exactly one edge each. Thus there cannot be a bichromatic cycle containing any of these colors. Now suppose there is a (i, j) bichromatic cycle with i > j and i, j / ∈ {0, 1, ∆ -1}. Note that 2 ≤ j. Then the edges have to be ua i , ua j and the cycle edges between them. It means that the cycle edges are adjacent, which means that i -j = 2. Hence we have d(a j a j+1 ) = i and d(a j+1 a i ) = j. Since i ≤ k -1, we infer that j + 1 ≤ k -3. Therefore by the definition of the coloring d, d(a j+1 a i ) = j + 3 > j, a contradiction. Thus the (i, j)-bichromatic cycle does not exist and thus coloring c is acyclic.

2

Therefore G has a desired coloring.

Fact 2 (

 2 [START_REF] Basavaraju | Acyclic edge coloring of 2-degenerate graphs[END_REF]) Let c be a partial coloring of G. A candidate color β is not valid for the edge e = (a, b) if and only if ∃α ∈ S ab ∩ S ba such that there is a (α, β, ab) critical path in G with respect to the coloring c.

case 1 :

 1 c (b 1 a 1 ) ∈ F xWithout loss of generality let c (xa 2 ) = c (b 1 a 1 ) = 1. Now since deg(x) = ∆, there exists only one candidate color for the edge a 1 x. Let it be α. Now if the color α is not valid, then by Fact 2, c(a 2 b 2 ) = α and there exists a (1, α, a 1 x) critical path containing the edge a 2 b 2 . If there exists a vertex a i other than a 1 , a 2 such that c (a i b i ) = α, then exchange the colors of edges xa 2 and xa i . Now by Lemma 1, the (1, α, a 1 x) critical path is broken and color α is valid for the edge a 1 x. If there is no such vertex a i , we have c(a i b i ) = α for all 3 ≤ i ≤ k. Let c (xa 3 ) = β. Now recolor the edge xa 3 using color α to get a coloring d. The coloring d is proper since α / ∈ F x (c ) and c (a 3 b 3 ) = α. It is also acyclic because if there is a bichromatic cycle created, then it has to be a (1, α)-bichromatic cycle, implying that there existed a (1, α, xa 3 ) critical path with respect to c , a contradiction to Fact 1 since there already existed a (1, α, a 1 x) critical path in c . Thus d is acyclic. Now we get a coloring c from d by assigning c (xa 3 ) = β for the edge xa 1 . The color is valid since any bichromatic cycle if present has to involve edges a 1 x, xa 2 , a 2 b 2 which are colored differently. Thus we have a valid coloring of G, a contradiction for the fact that G is a counterexample.

case 2 :

 2 c (b 1 a 1 ) / ∈ F xThis means that {c (b 1 a 1 ) = 1} ∪ F x = C. We have the following two subcases:2.1: c (a i b i ) = 1 for some i, 2 ≤ i ≤ k.Suppose without loss of generality that c (a i b i ) = α = 1 and c (xa i ) = β. Then recolor edge xa i using color 1 to get a coloring d. If the coloring d is valid we are in case 1. Otherwise a bichromatic cycle has been created due to this recoloring, say a (1, α)-bichromatic cycle going through b i , a i , a j , b j (for some j = i) with d(xa j ) = α and d(a j b j ) = 1.

Fig. 1 :

 1 Fig. 1: Coloring of G when G = K4

Acknowledgements

I am extremely grateful to the anonymous reviewers who helped in greatly improving the presentation of this paper.


Per Austrin

Siavosh Benabbas

Avner Magen

On Quadratic Threshold CSPs †

Keywords: Combinatorial Optimization, Approximation Algorithms, Constraint Satisfaction Problems

A predicate P : {-1, 1} k → {0, 1} can be associated with a constraint satisfaction problem MAX CSP(P ). P is called "approximation resistant" if MAX CSP(P ) cannot be approximated better than the approximation obtained by choosing a random assignment, and "approximable" otherwise. This classification of predicates has proved to be an important and challenging open problem. Motivated by a recent result of Austrin and Mossel (Computational Complexity, 2009), we consider a natural subclass of predicates defined by signs of quadratic polynomials, including the special case of predicates defined by signs of linear forms, and supply algorithms to approximate them as follows.

In the quadratic case we prove that every symmetric predicate is approximable. We introduce a new rounding algorithm for the standard semidefinite programming relaxation of MAX CSP(P ) for any predicate P : {-1, 1} k → {0, 1} and analyze its approximation ratio. Our rounding scheme operates by first manipulating the optimal SDP solution so that all the vectors are nearly perpendicular and then applying a form of hyperplane rounding to obtain an integral solution. The advantage of this method is that we are able to analyze the behaviour of a set of k rounded variables together as opposed to just a pair of rounded variables in most previous methods.

In the linear case we prove that a predicate called "Monarchy" is approximable. This predicate is not amenable to our algorithm for the quadratic case, nor to other LP/SDP-based approaches we are aware of.

Introduction

This paper studies the approximability of constraint satisfaction problems (CSPs). Given a predicate P : {-1, 1} k → {0, 1}, the MAX CSP(P ) problem is defined as follows. An instance is given by a list of k-tuples (clauses) of literals over some set of variables x 1 , . . . , x n , where a literal is either a variable or its negation. A clause is satisfied by an assignment to the variables if P is satisfied when applied to the value assigned to the k literals of the clause. The goal is then to find an assignment to the variables that maximizes the number of satisfied clauses. Our specific interest is predicates of the form P (x) = 1+sign(Q(x)) 2 where Q : R k → R is a quadratic polynomial with no constant term, i.e., † A preliminary version of this work appeared as [ABM10] ‡ Email: austrin@cs.toronto.edu. Work done while the author was at KTH, Stockholm, supported by ERC advanced investigator grant 226203.

§ Email: siavosh@cs.toronto.edu 1365-8050 c 2012 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France Q(x) = k i=1 a i x i + i =j b ij x i x j for some set of coefficients a 1 , . . . , a n and b 11 , . . . , b nn . While this special case is arguably very rich and interesting in its own right, we give some further motivations below. But first, we give some background to the study of MAX CSP(P ) problems in general.

A canonical example of a MAX CSP(P ) problem is when P (x 1 , x 2 , x 3 ) = x 1 ∨x 2 ∨x 3 is a disjunction of three variables, in which case MAX CSP(P ) is the classic MAX 3-SAT problem. Another well-known example is the MAX 2-LIN(2) problem in which P (x 1 , x 2 ) = x 1 ⊕ x 2 . As MAX CSP(P ) is NP-hard for almost all choices of P much effort has been put into understanding the best possible approximation ratio achievable in polynomial time. (i) A (randomized) algorithm is said to have approximation ratio α ≤ 1 if, given an instance with optimal value Opt, it produces an assignment with (expected) value at least α • Opt.

The arguably simplest approximation algorithm is to pick a uniformly random assignment. As this algorithm satisfies each constraint with probability |P -1 (1)| 2 k it follows that it gives an approximation ratio of

|P -1 (1)| 2 k
. In their classic paper [START_REF] Michel | Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming[END_REF], Goemans and Williamson used semidefinite programming to obtain improved approximation algorithms for predicates on two variables. For instance, for MAX 2-LIN(2) they gave an algorithm with approximation ratio α GW ≈ 0.878. Following [START_REF] Michel | Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming[END_REF], many new approximation algorithms were found for various specific predicates, improving upon the random assignment algorithm. However, for some cases, perhaps most prominently the MAX 3-SAT problem, no such progress was made. Then, in another classic paper Håstad [START_REF] Håstad | Some Optimal Inapproximability Results[END_REF] proved that MAX 3-SAT is in fact NP-hard to approximate within 7/8 + (for any constant > 0), showing that a random assignment in fact gives the best possible worst-case approximation that can be obtained in polynomial time.

Predicates which exhibit this behaviour are called approximation resistant. One of the main open questions along this line of research is to characterize which predicates admit a non-trivial approximation algorithm, and which predicates are approximation resistant. For predicates on three variables, the work of Håstad together with work of Zwick [START_REF] Zwick | Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables Per Constraint[END_REF] shows that a predicate is resistant iff it is implied by an XOR of the three variables, or the negation thereof, where a predicate P is said to imply a predicate P if P (x) = 1 ⇒ P (x) = 1. For four variables, Hast [START_REF] Hast | Beating a Random Assignment -Approximating Constraint Satisfaction Problems[END_REF] made an extensive classification leaving open the status of 46 out of 400 different predicates. It is worthwhile to note that in a celebrated result Raghavendra [START_REF] Raghavendra | Optimal Algorithms and Inapproximability Results For Every CSP?[END_REF] presents an approximation algorithm that (assuming the Unique Games Conjecture) achieves the best approximation factor for MAX CSP(P ) for any predicate P ; however, the approximation factor of this algorithm for any particular P is essentially impossible to understand and [START_REF] Raghavendra | Optimal Algorithms and Inapproximability Results For Every CSP?[END_REF] only proves that no other algorithm can do better (assuming the Unique Games Conjecture). (ii) Thus, this algorithm is not useful in determining which predicates are approximation resistant.

There have been several papers [ST00, EH08, ST09], mainly motivated by the soundness-query tradeoff for PCPs, giving increasingly general conditions under which predicates are approximation resistant. In a recent paper [START_REF] Austrin | Approximation Resistant Predicates from Pairwise Independence[END_REF], the first author and Mossel proved that, if there exists an unbiased pairwise independent distribution on {-1, 1} k whose support is contained in P -1 (1), then P is approximation resistant under the Unique Games Conjecture [START_REF] Khot | On the Power of Unique 2-prover 1-round Games[END_REF]. This condition is very general and turned out to give many new cases of resistant predicates [START_REF] Austrin | Randomly supported independence and resistance[END_REF]. A related result by Benabbas et al. [START_REF] Benabbas | SDP gaps from pairwise independence[END_REF] that is independent of complexity assumptions, shows that under the same condition on P , the so-called Sherali- (i) It follows from the dichotomy theorem of [START_REF] Creignou | A dichotomy theorem for maximum generalized satisfiability problems[END_REF] that (for any boolean predicate P ) MAX CSP(P ) is NP-hard unless P depends on at most 1 variable. (ii) [Rag08] also presents a (exponential time) algorithm to compute the approximation factor for a specific predicate P up to any required precision.

Adams SDP hierarchy-which is a strong version of the Semidefinite Programming approach-does not beat a random assignment. Indeed, when it comes to algorithms, there are very few systematic results that give algorithms for large classes of predicates. One such result can be found in [START_REF] Hast | Beating a Random Assignment -Approximating Constraint Satisfaction Problems[END_REF]. Given the result of [START_REF] Austrin | Approximation Resistant Predicates from Pairwise Independence[END_REF], assuming the Unique Games Conjecture, such systematic results can only work for predicates that do not support pairwise independence. A very natural subclass of these predicates are those of the form 1+sign(Q) 2 for Q a quadratic polynomial as described above. To be more precise, the following fact from [START_REF] Austrin | Randomly supported independence and resistance[END_REF] is our main motivation for studying this type of predicates. Fact 1. A predicate P does not support pairwise independence if and only if there exists a quadratic polynomial Q : {-1, 1} k → R with no constant term that is positive on all of P -1 (1) (in other words, P implies a predicate of the form 1+sign(Q)

2

).

Given that the main tool for approximation algorithms-semidefinite programming-works by optimizing quadratic forms, it seemed natural and intuitive to hope that predicates of this form are always approximable. This however turns out to be false-in [START_REF] Austrin | On the Usefulness of Predicates[END_REF], a predicate is constructed that is the sign of a quadratic polynomial and still approximation resistant assuming the Unique Games Conjecture. Loosely speaking, the main crux is that semidefinite programming is good for optimizing the degree-2 part of the Fourier expansion of a predicate, which unfortunately can behave very differently from P itself or the quadratic polynomial used to define P (we elaborate on this below.) However, it turns out that when we restrict our attention to the special case of signs of symmetric polynomials (i.e., polynomials which are invariant under any permutation of their variables), this can not happen, and we can obtain an approximation algorithm, which is our first result.

Theorem 1. Let P : {-1, 1} k → {0, 1} be a predicate that is of the form P (x) = 1+sign(Q(x)) 2
where Q is a symmetric quadratic polynomial with no constant term. Then P is not approximation resistant.

A very natural special case of the signs of (not necessarily symmetric) quadratic polynomials is the case when P (x) is simply the sign of a linear form, i.e., a linear threshold function. While we cannot prove that linear threshold predicates are approximable in general, we do believe this is the case, and make the following conjecture.

Conjecture 1. Let P : {-1, 1} k → {0, 1} be a predicate that is a sign of a linear form with no constant term. Then P is not approximation resistant.

We view the resolution of this conjecture as a very natural and interesting open problem. As in the quadratic case, the difficulty stems from the fact that the low-degree part of P can be unrelated to the linear form used to define P . Specifically, it can be the case that the low-degree part of the arithmetization of P vanishes or becomes negative for some inputs where the linear/quadratic polynomial is positive (i.e. accepting inputs), and unfortunately this seems to make the standard SDP approach fail. The perhaps most extreme case of this phenomenon is exhibited by the predicate Monarchy : {-1, 1} k → {0, 1} suggested by Håstad [START_REF] Håstad | [END_REF], in which the first variable (the "monarch") decides the outcome, unless all the other variables unite against it. In other words,

Monarchy(x) = 1 + sign((k -2)x 1 + k i=2 x i ) 2 .
Now, for the input x 1 = -1, x 2 = . . . = x k = 1, the linear part of the Fourier expansion of Monarchy takes value -1 + o k (1), whereas the linear form used to define monarchy is positive on this input, hence the value of the predicate is 1. Again, we stress that this means that known algorithms and techniques to obtain explicit bounds do not apply (while the results of Raghavendra [START_REF] Raghavendra | Optimal Algorithms and Inapproximability Results For Every CSP?[END_REF] in theory allow us to pin down the approximability to within any desired precision, they are not practical enough to let us determine whether a given predicate is approximation resistant (iii) ). However, in this case we are still able to achieve an approximation algorithm, which is our second result.

Theorem 2. The predicate Monarchy is not approximation resistant.

This shows that there is some hope in overcoming the apparent barriers to proving Conjecture 1.

A recent related work of Cheraghchi et al. [START_REF] Cheraghchi | Approximating linear threshold predicates[END_REF] also studies the approximability of predicates defined by linear forms. However, their focus is on establishing precise quantitative bounds on the approximability, rather than the more qualitative distinction between approximable and approximation resistant predicates. As such, their results only apply to predicates which were already known to be approximable. Specifically, they consider "Majority-like" predicates P where the linear part of the Fourier expansion of P behaves similarly to P itself (in the sense explained above).

Techniques: Our starting point in both our algorithms is the standard SDP relaxation of MAX CSP(P ). The main difficulty in rounding the solutions of these SDPs is that current rounding algorithms offer no analysis of the joint distribution of the outcome of the rounding for k variables, when k > 2. (Interestingly, when some modest value k = 3 is used, often some numerical methods are employed to complete the analysis [START_REF] Karloff | A 7/8-Approximation Algorithm for MAX 3SAT?[END_REF][START_REF] Zwick | Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables Per Constraint[END_REF].) Unfortunately, such analysis seems essential to understanding the performance of the algorithm for MAX CSP(P ) as each constraint depends on k variables. Indeed, even a local argument would have to argue about the outcome of the rounding algorithm for k variables together.

For Theorem 1, we give a new and more direct proof of a theorem by Hast [START_REF] Hast | Beating a Random Assignment -Approximating Constraint Satisfaction Problems[END_REF], giving a general condition on the low-degree part of the Fourier Expansion which guarantees a predicate is approximable (Theorem 4). We then show that this condition holds for predicates which are defined by symmetric quadratic polynomials. The basic idea behind our new algorithm is as follows. First, observe that the SDP solution in which all vectors are perpendicular is easy to analyze when the usual hyperplane rounding is employed, as in this case the obtained integral values are distributed uniformly. This motivates the following approach: start with the perpendicular configuration and then perturb the vectors in the direction of the optimal SDP solution. This perturbation acts as a differentiation operator, and as such allows for a "linear snapshot" of what is typically a complicated system. For each clause we analyze the probability that hyperplane rounding outputs a satisfying assignment, as a function of the inner products of vectors involved. Now, the object of interest is the gradient of this function at "zero". The hope is that since the optimal SDP solution (almost) satisfies this clause, it has a positive inner product with the gradient, and so can act as a global recipe that works for all clauses. It is important to stress that since we are only concerned with getting an approximation algorithm that works slightly better than random we can get away with this linear simplification. We show that this condition on the gradient translates into a condition on the low-degree part of the Fourier expansion of the predicate.

As it turns out, the predicate Monarchy which we tackle in Theorem 2 does not exhibit the aforementioned desirable property. In other words, the gradient above does not generally have a positive inner product with an optimal SDP solution. Instead, we show that when all vectors are sufficiently far from ±v 0 it is possible to get a similar guarantee on the gradient using high (but not too high) moments of the (iii) In fact it is not even known whether, given a predicate P , it is decidable to check if P is approximation resistant. vectors. We can then handle vectors which are very close to ±v 0 separately by rounding them deterministically to ±1.

Organization: The rest of the paper is organized as follows. First, we introduce some definitions and preliminaries including the standard SDP relaxation of MAX CSP(P ) in Section 2. Then, in Section 3 we give our new algorithm for this SDP relaxation and characterize the predicates for which it gives an approximation ratio better than a random assignment. We then take a closer look at signs of symmetric quadratic forms in Section 4 and show that these satisfy the condition of the previous section, proving Theorem 1. In Section 5 we give the approximation algorithm for the Monarchy predicate and its somewhat tedious analysis. Finally, we give a discussion and some directions for future work in Section 6.

Preliminaries

In what follows E stands for expectation. For any positive integer n we use the notation [n] for the set {1, . . . , n}. For a finite set S (often a subset of [n]) we use the notation {-1, 1} S for the set of all -1, 1 vectors indexed by elements of S. For example, |{-1, 1} S | = 2 |S| . When x ∈ {-1, 1} S and y ∈ {-1, 1} S are two vectors indexed by disjoint sets, i.e. S ∩ S = ∅, we use x • y ∈ {-1, 1} S∪S to denote their natural concatenation.

We use ϕ and Φ for the probability density function and the cumulative distribution function of a standard normal random variable, respectively. We use the notation S n for the n + 1 dimensional sphere, i.e. , the set of unit vectors in R n+1 .

Throughout the paper, we use sign(x) for the sign function defined as,

sign(x) = 1 x > 0, -1 x ≤ 0.
Note that sign(0) = -1.

Fourier Representation

Consider the set of real functions with domain {-1, 1} k as a vector space. It is well known that the following set of functions called the characters form a complete basis for this space, χ S (x)

def = i∈S x i .
In fact if we define inner products of functions as f

• g def = E x [f (x)g(x)
] this basis will be orthonormal and every function will have a unique Fourier expansion when written in this basis,

f = S⊆[k] f (S)χ S , f (S) def = f • χ S .
The values f (S)

S⊆[n]
are often called the Fourier coefficients of f . We write f =d for the part of the function that is of degree d, i.e., Maximize

f =d (x) = |S|=d f ({S})χ S (x).
1 m m i=1 ω∈{-1,1} T i C i (ω) I Ti,ω
Where,

∀S ⊂ [n], |S| ≤ k, ω ∈ {-1, 1} S I S,ω ∈ [0, 1] ∀i ∈ [n] v i ∈ S n v 0 ∈ S n Subject to ∀S ⊂ [n], |S| ≤ k ω∈{-1,1} S I S,ω = 1 (1) ∀S ⊂ S ⊂ [n], |S | ≤ k, ω ∈ {-1, 1} S ω ∈{-1,1} S \S I S ,ω •ω = I S,ω (2) ∀i ∈ [n] I {i},(1) -I {i},(-1) = v 0 • v i (3) ∀i, j ∈ [n] I {i,j},(1,1) -I {i,j},(-1,1) -I {i,j},(1,-1) + I {i,j},(-1,-1) = v i • v j (4)
It is easy to see that whenever

f : {-1, 1} k → R is odd (i.e. f (x) = -f (-x)) and S ⊆ [k] is an even sized set f (S) = 0: f (S) = E x [f (x)χ S (x)] = -E x [f (-x)χ S (x)] = -E x [f (-x)χ S (-x)] = -E y [f (y)χ S (y)] = -f (S),
where we have used the fact that χ S is an even function for even |S|.

Semidefinite Relaxation

For any fixed P , MAX CSP(P ) has a natural SDP relaxation that can be seen in Figure 1. The essence of this relaxation is that each I S, * is a distribution, often called a local distribution, over all possible assignments to the variables in set S as enforced by (1). Whenever, S 1 and S 2 intersect (2) guarantees that their marginal distributions on the intersection agree. Also, (3) and (4) ensure that v 0 • v i and v i • v j are equal to the bias of variable x i and the correlation of the variables x i and x j in the local distributions respectively. The clauses of the instance are C 1 , . . . , C m , with C i being an application of P (possibly with some variables negated) on the set of variables T i . The objective function is the fraction of the clauses that are satisfied.

Observe that the reason this SDP is not an exact formulation but a relaxation is that these distributions are defined only on sets of size up to k. It is worth mentioning that this program is weaker than the kth round of the Lasserre hierarchy for this problem while stronger than the kth round of the Sherali-Adams hierarchy. From here on the only things we use in the rounding algorithms are the vectors v 0 , . . . , v n and the existence of the local distributions.

( , η)-hyperplane rounding

In this section we define a rounding scheme for the semidefinite program of MAX CSP(P ) and proceed to analyze its performance. The rounding scheme is based on the usual hyperplane rounding but is more flexible in that it uses two parameters ≥ 0 and η where is a sufficiently small constant and η is an arbitrary real number. We will then formalize a (sufficient) condition involving P and η under which our approximation algorithm has approximation factor better than that of a random assignment. In the next section we show that this condition is satisfied (for some η) by signs of symmetric quadratic polynomials.

Given an instance of MAX CSP(P ), our algorithm first solves the standard SDP relaxation of the problem (Figure 1.) It then employs the rounding scheme outlined in Figure 2 to get an integral solution.

INPUT: v 0 , v 1 , . . . , v n ∈ S n . OUTPUT: x 1 , . . . , x n ∈ {-1, 1}.
1. Define unit vectors w 0 , w 1 , . . . , w n ∈ S n such that for all 0 ≤ i < j,

w i • w j = (v i • v j ), 2. Let g ∈ R n+1 be a random (n + 1)-dimensional Gaussian.
3. Assign each x i as,

x i = 1 if w i • g > -η(w 0 • w i ), -1 otherwise.
Note that when = 0 the rounding scheme above simplifies to assigning all x i 's uniformly and independently at random which satisfies |P -1 (1)| fraction of all clauses in expectation. For non-zero , η will determine how much weight is given to the position of v 0 compared to the correlation of the variables.

Notice that in the pursuit of a rounding algorithm that has approximation ratio better than

|P -1 (1)| 2 k
it is possible to assume that the optimal integral solution is arbitrary close to 1 as otherwise random assignment already delivers an approximation factor better than

|P -1 (1)| 2 k
. In particular, the optimal vector solution can be assumed to be that good. This observation is in fact essential to our analysis. Let us for the sake of simplicity first consider the case where the value of the vector solution is precisely 1. Fix a clause, say P (x 1 , x 2 , . . . , x k ). (In general, without loss of generality we can assume that the current clause is on k variables as opposed to k literals. This is simply because one can assume that ¬x i is a separate variable from x i with SDP vector -v i .) Since the SDP value is 1, every clause (and this clause in particular) is completely satisfied by the SDP, hence the local distribution I [k], * is supported on the set of satisfying assignments of P . The hope now is that when increases from zero to some small positive value this distribution helps to boost the probability of satisfying the clause (a little) beyond

|P -1 (1)| 2 k
. This becomes a question of differentiation. Specifically, consider the probability of satisfying the clause at hand as a function of . We want to show that for some > 0 the value of this function is bigger than its value at zero. This is closely related to the derivative of the function at zero and in fact the first step is to analyze this derivative. The following Theorem relates the value of this function and its derivative at zero to the predicate P and the vectors v 0 , v 1 , . . . , v k .

Theorem 3. For any fixed η, the probability that P (x 1 , . . . , x k ) is satisfied by the assignment behaves as follows at = 0:

Pr (x 1 , . . . , x k ) ∈ P -1 (1) = |P -1 (1)| 2 k d d Pr (x 1 , . . . , x k ) ∈ P -1 (1) = 2η √ 2π k i=1 P ({i})v 0 • v i + 2 π i<j P ({i, j})v i • v j . (5)
Proof: The first claim follows from the fact that for = 0, x 1 , . . . , x k are uniform and independent. To prove (5) we first introduce some notation. For an assignment ω ∈ {-1, 1} k define the function p ω on (k + 1) × (k + 1) semidefinite matrices as follows. For a positive semidefinite matrix A (k+1)×(k+1) , consider a set of vectors w 0 , . . . , w k whose Gram matrix is A, and consider running steps 2 and 3 of the rounding procedure on w i 's instead of w i 's. Define p ω (A) as the probability that the rounding procedure outputs ω. In what follows, we will use A * = A * ( ) to denote the Gram matrix of the set of vectors w 1 , . . . , w n used by the algorithm (which depends on ). Clearly, we have that

Pr (x 1 , . . . , x k ) ∈ P -1 (1) = ω∈P -1 (1) Pr [(x 1 , . . . , x k ) = ω] = ω∈P -1 (1)
p ω (A * ).

We start by computing d d p ω (A * ) using the chain rule.

d d p ω (A * ( )) = i≤j d d a * ij =0 • ∂ ∂a ij p ω (A) A=I = i<j v i • v j ∂ ∂a ij p ω (A) A=I , (6)
where when we talk about ∂ ∂aij p ω (A) we consider A a symmetric positive semidefinite matrix so a ji changes with a ij . Now to compute ∂ ∂aij p ω (A) A=I we compute a formula for p ω (A) where A is equal to I in every entry except the ij and ji entries where it is a ij . Define J ij as the matrix which is zero on every coordinate except coordinates ij and ji where it is 1. Then,

∂ ∂a ij p ω (A) A=I = d dt p ω (I + tJ ij ) t=0 .
Note that for t ∈ [-1, 1], I +tJ is positive semidefinite, so p ω (I +tJ) is well-defined. Now observe that the geometric realization of w 0 , . . . , w k defining p ω (I + tJ ij ) is simple; in particular, all the vectors are perpendicular except the pair w i and w j , so p ω (I + tJ ij ) can be readily computed using a case analysis, with two cases depending on whether i or j equals zero, as follows.

First, if i = 0, the value of all variables are going to be assigned independently, and all but x j are going to be assigned values uniformly. It is easy to see that for any j ∈ [k] and any ω ∈ {-1, 1} k ,

p ω (I + tJ 0j ) = 2 -(k-1) • Pr w j • g ≥ -ηt if ω j = 1 Pr w j • g ≤ -ηt if ω j = -1 = 2 -(k-1) • 1 -Φ(-ηt) if ω j = 1 Φ(-ηt) if ω j = -1 = 2 -(k-1) • 1 + ω j 2 -ω j Φ(-ηt) .
Differentiating, we get

d dt p ω (I + tJ 0j ) = -2 -(k-1) ω j d dt Φ(-ηt) = 2 -(k-1) ηω j ϕ(-ηt) = 2 -(k-1) ηω j e -η 2 t 2 /2 √ 2π ,
from which we get the identity

∂ ∂a 0j p ω (A) A=I = 2 -(k-1) ηω j √ 2π . (7)
Let us then consider the case where both i and j are non-zero. In this case, each variable is going to be assigned a value in {-1, 1} uniformly at random, and all these assignments are independent except the assignments of the ith and the jth variable. So we can imagine that x l for all l ∈ {i, j} are assigned a uniformly independent value in {-1, 1} and then x i and x j are assigned random values depending only on g projected to the linear subspace spanned by w i and w j ; we will use g for this projection. The joint distribution of x i and x j is then not hard to understand: x i is uniformly random and x j = x i if and only g lies in one of two segment of the unit circle (in this linear subspace) shown in Figure 3. We note that this analysis is identical to the one used by [START_REF] Michel | Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming[END_REF]. We have,

p ω (I + tJ ij ) = 2 -(k-1) • 1 π arccos t if ω i = ω j 1 -1 π arccos t if ω i = ω j = 2 -(k-1) ( 1 + ω i ω j 2 - 1 π ω i ω j arccos t)
Differentiating this expression, we have

d dt p ω (I + tJ ij ) = - 2 -(k-1) ω i ω j π • d dt arccos t = 2 -(k-1) ω i ω j π √ 1 -t 2 ,
and we can conclude that

∂ ∂a ij p ω (A) A=I = 2 -(k-1) ω i ω j /π. (8)
w i w j Now combining (6) with ( 7) and (8) we get,

d d Pr (x 1 , . . . , x k ) ∈ P -1 (1) = ω∈P -1 (1) i<j v i • v j ∂ ∂a ij p ω (A) A=I = 1≤i≤k v 0 • v i 2 -(k-1) η √ 2π ω∈P -1 (1) ω i + 1≤i<j≤k v i • v j 2 -(k-1) π ω∈P -1 (1) ω i ω j = 1≤i≤k v 0 • v i 2η √ 2π E ω [ω i P (ω)] + 1≤i<j≤k v i • v j 2 π E ω [ω i ω j P (ω)] = 2η √ 2π k i=1 P ({i})v 0 • v i + 2 π i<j P ({i, j})v i • v j .
Which completes the proof. Now, the inner products v i • v j are equal to the moments of the local distributions I {i,j}, * , which in turn agree with those of the local distribution

I [k], * . It follows that, 2η √ 2π k i=1 P ({i})v 0 • v i + 2 π i<j P ({i, j})v i • v j = E ω∼I [k], * 2η √ 2π P =1 (ω) + 2 π P =2 (ω) . (9)
Thus, in order for the derivative in (5) to be positive for all possible values of the v i 's (that have SDP objective value 1), it is necessary and sufficient that 2η √ 2π P =1 (ω) + 2 π P =2 (ω) is positive for every ω ∈ P -1 (1). This leads us to the following Theorem formulating a condition under which our rounding algorithm works.

Theorem 4. Suppose that there exists an η ∈ R such that

2η √ 2π P =1 (ω) + 2 π P =2 (ω) > 0 ( 10
)
for every ω ∈ P -1 (1). Then P is approximable.

As mentioned in the Techniques section, this theorem is not new. It was previously found by Hast [START_REF] Hast | Beating a Random Assignment -Approximating Constraint Satisfaction Problems[END_REF]. However, his algorithm and analysis are completely different from ours (using different algorithms to optimize the linear and quadratic parts of the predicate, and case analysis depending on the behaviour of the integral solution). We believe that our algorithm is simpler and considerably more direct.

The general strategy for the proof, which can be found below, is as follows. We will concentrate on a clause that is almost satisfied by the SDP solution. By Equation 10 and Theorem 3 the first derivative of the probability that this clause is satisfied by the rounded solution is at least some positive global constant (say δ) at = 0. We will then show that for small enough the second derivative of this probability is bounded in absolute value by, say, Γ at any point in [0, ]. Now we can apply Taylor's theorem to show that if is small enough the probability of success is at least

|P -1 (1)| 2 k + δ -Γ 2 /2 which for = δ/Γ is at least |P -1 (1)| 2 k + δ 2 /2Γ.
Proof of Theorem 4: Consider the optimal vector solution v 1 , . . . , v n ∈ S n . Note that the optimal integral solution will have objective value no more than that of v 0 , . . . , v n . So if we fix a constant δ 2 , we can always assume that the vector solution achieves objective value at least 1 -δ 2 . Otherwise, a random assignment to the variables will achieve an objective value of

|P -1 (1)| 2 k
and approximation factor

|P -1 (1)| 2 k /(1 -δ 2 ) > |P -1 (1)| 2 k
(1 + δ 2 ). So, in this case even a random assignment shows that the predicate is not approximation resistant. From here on we assume that the vector solution achieves an objective value of 1 -δ 2 , where δ 2 is some constant to be set later. Now, applying a simple Markov type inequality one can see that at least a 1 -√ δ 2 fraction of the clauses must have SDP value at least 1 -√ δ 2 . Consider one such clause, say P (x 1 , . . . , x k ). We will show that the probability that this clause is satisfied by the rounded solution is slightly more than |P -1 (1)| 2 k . Let δ 1 > 0 be the minimum value of the left hand side of (10) over all ω ∈ P -1 (1), and let s denote its minimum over all ω ∈ {-1, 1} k . By Theorem 3 and (9), we have

d d Pr (x 1 , . . . , x k ) ∈ P -1 (1) = 2η √ 2π j>0 P ({j})v j • v 0 + 2 π 0<i<j P ({i, j})v i • v j = E ω∼I [k], * 2η √ 2π P =1 (ω) + 2 π P =2 (ω) ≥ (1 -δ 2 )δ 1 + δ 2 s ≥ δ 1 /2
where the last step holds provided δ 2 is sufficiently small (iv) compared to δ 1 and s. This shows that the first derivative (at = 0) of the probability that P is satisfied by the rounded solution is bounded from below by the constant δ 1 /2.

All that remains is to show that the second derivative of this probability can not be too large in absolute value. We will need the following lemma about the second derivative of the orthant probability of normal random variables. Lemma 5. For fixed k, define the function ort(ν, Σ) as the orthant probability of the multivariate normal distribution with mean ν and covariance matrix Σ, where ν ∈ R k and Σ k×k is a positive semidefinite matrix. That is, ort(ν, Σ)

def = Pr x∼N (ν,Σ) [x ≥ 0] .
There exists a global constant Γ that upper bounds all the second partial derivatives of ort() when Σ is close to I. In particular, for all k, there exist κ > 0 and Γ, such that for all i 1 , j 1 , i 2 , j 2 ∈ [k], all vectors ν ∈ R k and all positive definite matrices Σ k×k satisfying

|I -Σ| ∞ , |ν| ∞ < κ, we have, ∂ 2 ∂Σ i1j1 ∂Σ i2j2 ort(ν, Σ) < Γ, ∂ 2 ∂Σ i1j1 ∂ν i2 ort(ν, Σ) < Γ, ∂ 2 ∂ν i1 ∂ν i2 ort(ν, Σ) < Γ.
The proof of this lemma is rather technical, but the general outline is as follows. First we write down the orthant probability as an integral of the probability density function over the positive orthant. Then we observe that each of the inner integrals as well as the probability density function and their partial derivatives are continuous, so we can apply Leibniz's integral rule iteratively to move the differentiation under the integral. We then differentiate the probability density function and the result will be in the form of the expectation of a degree 2 expression in x i 's under the same distribution. We can then bound these expression in terms of the means and correlations of the variables. For the interested reader a full proof is presented in an appendix. Now, similar to the proof of Theorem 3 we can write,

d 2 d 2 Pr (x 1 , . . . , x k ) ∈ P -1 (1) = d d ω∈P -1 (1) 0≤i<j≤k v i • v j ∂ ∂a ij p ω (A) = ω∈P -1 (1) 0≤i<j≤k v i • v j 0≤i <j ≤k v i • v j ∂ 2 ∂a ij ∂a i j p ω (A). (11)
One can think of g • w 1 + ηw 0 • w 1 , g • w 1 + ηw 0 • w 2 , . . . as a set of joint Gaussian random variables.

In particular for a fixed ω define ν ∈ R n and a positive definite matrix Σ k×k as,

∀1 ≤ i ≤ k ν i = ηA 0i ω i = ηω i v 0 • v i ∀1 ≤ i ≤ k Σ ii = 1 ∀1 ≤ i < j ≤ k Σ ij = Σ ji = A ij ω i ω j = ω i ω j v i • v j
It is easy to verify that p ω (A) is indeed the orthant probability of Gaussian distribution with mean ν and correlation matrix Σ. So according to Lemma 5 and (11) for ≤ min(κ, κ/|η|),

d 2 d 2 Pr (x 1 , . . . , x k ) ∈ P -1 (1) ≤ 2 k k 4 Γ,
where 2 k k 4 is a bound on the number of terms in (11) and κ and Γ are constants only depending on k. Now for every such 0 according to Taylor's theorem for some 0 ≤ ≤ 0 , Pr (x 1 , . . . , x k ) ∈ P -1 (1)

= 0 = |P -1 (1)| 2 k + 0 d d Pr (x 1 , . . . , x k ) ∈ P -1 (1) =0 + 2 0 2 d 2 d 2 Pr (x 1 , . . . , x k ) ∈ P -1 (1) = ≥ |P -1 (1)| 2 k + 0 δ 1 /2 -2 0 2 k k 4 Γ/2.
Setting 0 appropriately (v) , this is at least

|P -1 (1)| 2 k
+ δ 3 for δ 3 = 0 δ 1 /4 (which crucially does not depend on δ 2 ). This shows that each clause for which the vector solution gets a value of (1 -√ δ 2 ) is going to be satisfied by the rounded solution with probability at least

|P -1 (1)| 2 k + δ 3 .
As these constitute a 1 -√ δ 2 fraction of all clauses, the overall expected value of the objective function for the rounded solution is at least

1 -δ 2 |P -1 (1)| 2 k + δ 3 ≥ |P -1 (1)| 2 k + δ 3 -δ 2 .
If we set δ 2 < (δ 3 /2) 2 , this is at least |P -1 (1)| 2 k +δ 3 /2, which provides a lower bound on the approximation ratio of the algorithm on instances with optimal value at least 1 -δ 2 . This completes the proof.

Signs of Symmetric Quadratic Polynomials

In this section we study signs of symmetric quadratic polynomials, and give a proof of Theorem 1. Consider a predicate P : {-1, 1} k → {0, 1} that is the sign of a symmetric quadratic polynomial with no constant term, i.e., P (x) = 1 + sign α i x i + β i<j x i x j 2 for some constants α and β. We would like to apply the ( , η)-rounding scheme to MAX CSP(P ), which in turn requires us to understand the low-degree Fourier coefficients of P . Note that because of symmetry, the value of a Fourier coefficient P (S) depends only on |S|.

We will prove that "morally" β has the same sign as the degree-2 Fourier coefficient of P and that if one of them is 0 then so is the other. This statement is not quite true (consider for instance the predicate

P (x 1 , x 2 ) = 1+sign(x1+x2) 2 = 1+x1+x2+x1x2 4
), however it is always true that by slightly adjusting β (without changing P ), we can assure that this is the case.

(v) 0 = min(κ, κ/|η|, 2 -k k -2 δ 1 /2Γ) will do Theorem 6. For any P of the above form, there exists β with the property that β • P ({1, 2}) ≥ 0 and β = 0 iff P ({1, 2}) = 0, satisfying

P (x) = 1 + sign (α x i + β x i x j ) 2 .
Proof: Let us define

P β (x) = 1 + sign(α x i + β x i x j
) 2 where we consider α fixed and β as a variable. First, we have the following claim:

Claim 1. P β ({1, 2}
) is a monotonically non-decreasing function in β. Furthermore, if P β1 = P β2 then P β1 ({1, 2}) = P β2 ({1, 2}).

Proof: Fix two arbitrary values β 1 < β 2 of β, and let ∆P : {-1, 1} k → {-1, 0, 1} be the difference ∆P = P β2 -P β1 . Consider an input x ∈ {-1, 1} k . It follows from the definition of P β that if ∆P (x) > 0 then i<j x i x j > 0, and similarly if ∆P (x) < 0 then i<j x i x j < 0. Now since ∆P is symmetric, the level-2 Fourier coefficient of ∆P equals ,

∆P ({1, 2}) = 1 n 2 i<j ∆P ({i, j}) = 1 n 2 E x   ∆P (x) i<j x i x j   ≥ 0,
with equality holding only if ∆P is zero everywhere, i.e., if P β1 = P β2 . This completes the proof of the Claim.

Suppose first that either α = 0 or k is odd. It is easy to check that in these two cases, P 0 ({1, 2}) = 0 (if α = 0 the function P 0 is constant, and if α = 0 but k is odd the function P 0 is odd so its Fourier coefficients of size 2 are zero). Consider the set of values B = { β | P β ({1, 2}) = 0 }. From Claim 1 it follows that B is an interval (though it is possible for this interval to consist of a single point) and that the function P β is the same for all β ∈ B. For β < 0, β ∈ B, Claim 1 shows that P β ({1, 2}) < 0 and so has the same sign as β, and similarly for β > 0, β ∈ B. For β ∈ B we see that P β = P 0 and thus we can set β = 0.

The remaining case is that of even k, and α = 0. Notice that if |β| is sufficiently small compared to |α|, say, |β| ≤ |α|/k 2 , then P β (x) only differs from P 0 (x) on balanced inputs (i.e., having

x i = 0). Let B be the set of all such sufficiently small β's. For β ∈ B, the only contribution to P β ({1, 2}) comes from points x that are balanced (i.e., having x i = 0). The reason is that for all other x, the contribution sign(α x i )x 1 x 2 to P 0 ({1, 2}) is cancelled by the contribution from the point -x.

For balanced points, we have

i<j x i x j = 2 n/2 2 -(n/2) 2 = -n 2 < 0 and therefore sign(α x i + β x i x j ) = sign(-β), implying i<j P β ({i, j}) = 2 -k x: xi=0 i<j sign(-β)x i x j ,
which has the same sign as -sign(-β). Thus we see that if β > 0, β ∈ B we have P β ({1, 2}) > 0, and if β ≤ 0, β ∈ B we have P β ({1, 2}) < 0.

From Claim 1 it follows that whenever β = 0 (not necessarily in B) we can simply take β = β, and that when β = 0 we can take β to be a negative value close to 0 (e.g., β = -|α|/k 2 ).

We are now ready to prove Theorem 1.

Theorem 1 (restated). Let P : {-1, 1} k → {0, 1} be a predicate that is of the form

P (x) = 1+sign(Q(x)) 2
where Q is a symmetric quadratic polynomial with no constant term. Then P is not approximation resistant.

Proof: Without loss of generality, we can take Q(x) = α x i + β x i x j where β satisfies the property of β in Theorem 6.

If P ({1, 2}) = β = 0, we set η = α/ P ({1}) (note that in this case we can assume that α, and hence also P ({1}) is non-zero as otherwise P is the trivial predicate that is always false). We then have, for every x ∈ P -1 (1), 2η

√ 2π P =1 (x) + 2 π P =2 (x) = 2α √ 2π x i ,
which is positive by the definition of P . If P ({1, 2}) = 0, we set η = 2

π α P ({1}) • P ({1,2}) β . In this case for every x ∈ P -1 (1), 2η √ 2π P =1 (x) + 2 π P =2 (x) = 2 P ({1, 2}) πβ α x i + β x i x j > 0,
since β agrees with P ({1, 2}) in sign and Q(x) > 0. In either cases, using Theorem 4 and the respective choices of η we conclude that P is approximable.

Monarchy

In this section we prove that for k > 4 the Monarchy predicate is not approximation resistant. Notice that Monarchy is defined only for k > 2, and that the case k = 3 coincides with the predicate majority that is known not to be approximation resistant. Further, the case k = 4 is handled by [START_REF] Hast | Beating a Random Assignment -Approximating Constraint Satisfaction Problems[END_REF]. (vi) Just like the algorithm of Theorem 4 we first solve the natural semidefinite program of Monarchy, and then use a rounding algorithm to construct an integral solution out of the vectors. The rounding algorithm, which is given in Figure 4, has two parameters > 0 and an odd positive integer , both depending on k. These will be fixed in the proof.

Remark 1. As the reader may have observed, the "geometric" power of SDP is not used in the rounding scheme in Figure 4, and indeed a linear programming relaxation of the problem would suffice for the algorithm we propose. However, in the interest of consistency and being able to describe the techniques in a language comparable to Theorem 1 we elected to use the SDP framework.

= v 0 • v 1 , . . . , b n = v 0 • v n .
PARAMETERS: An odd integer and ∈ [0, 1].

OUTPUT: x 1 , . . . , x n ∈ {-1, 1}. 1. Choose a parameter τ ∈ [1/(2k 2 ), 1/k 2 ] uniformly at random. 2. For all i, (a) If b i > 1 -τ or b i < -1 + τ , set x i to 1 or -1 respectively.
(b) Otherwise, set x i (independent of all other x j 's), randomly to -1 or

1 such that E [x i ] = b i . In particular, set x i = 1 with probability (1 + b i )/2 and x i = -1 with probability (1 -b i )/2.
We will first discuss the intuition behind the analysis of the algorithm ignoring, for now, the greedy ingredient (2a above). Notice that for = 0 the rounding gives a uniform assignment to the variables, hence the expected value of the obtained solution is 1/2. As long as > 0 is small enough, the probability of success for a clause is essentially only affected by the degree-one Fourier coefficients of Monarchy. Now, fix a clause and assume that the SDP solution completely satisfies it. Specifically, consider the clause Monarchy(x 1 , . . . , x k ), and define b 1 , . . . , b k as the corresponding biases. As the analysis will show, the rounding scheme above satisfies Monarchy(x 1 , . . . , x k ) with a probability that is essentially 1/2 plus some positive linear combination of the b i . Our objective is then to fix that would make the value of this combination positive (and independent from n). It turns out that the maximal b i in magnitude (call it b j ) is always positive in this case. Oversimplifying, imagine that |b j | ≥ |b i | + ξ for all i different than j where ξ is some positive constant. In this setting it is easy to take (a function of k) that makes the effect of all b i other than b j vanish, ensuring a positive addition to the probability as desired so that overall the expected fraction of satisfied clauses is more than 1/2.

More realistically, the above slack ξ does not generally exist. However, we can show that a similar condition holds provided that the |b i | are bounded away from 1. This condition suffices to prove that the rounding algorithm works for clauses that do not have any variables with bias very close to ±1. The case where there are b i that are very close to 1 in magnitude is where the greedy ingredient of the algorithm (2a) is used, and it can be shown that when τ is roughly 1/k 2 , this ingredient works. In particular, we can show that for each clause, if rule (2a) is used to round one of the variables, it is used to round essentially every variable in the clause. Also, if this happens, the clause is going to be satisfied with high probability by the rounded solution.

The last complication stems from the fact that the clauses are generally not completely satisfied by the SDP solution. However, a standard averaging argument implies that it is enough to deal with clauses that are almost satisfied by the SDP solution. For any such clause the SDP induces a probability distribution on the variables that is mostly supported on satisfying assignments, compared to only on satisfying assignments in the above ideal setting. As such, the corresponding b i 's can be thought of as a perturbed version of the biases in that ideal setting. Unfortunately, the greedy ingredient of the algorithm is very sensitive to such small perturbations. In particular, if the biases are very close to the set threshold, τ , a small perturbation can break the method. To avoid this, we choose the actual threshold randomly, and we manage to argue that only a small fraction of the clauses end up in such unfortunate configurations.

This completes the high level description of the proof of our second result. Theorem 2 (restated). The predicate Monarchy is not approximation resistant.

Proof: As in Theorem 4 we can assume that the objective value of the SDP solution is at least 1 -δ for a fixed constant δ to be set later, and we can focus on clauses with SDP value at least 1 -√ δ. Again, as in Theorem 4 we consider one of these constraints and without loss of generality assume that this constraint is on x 1 , . . . , x k . Remember that the variables

I [k], * define a distribution, say µ, on {-1, 1} k such that Pr y∼µ [Monarchy(y) = 1] ≥ 1 - √ δ, ∀i b i = E y∼µ [y i ] .
Given that we choose τ uniformly at random in an interval of length 1/(2k 2 ), for any particular clause the probability that |b 1 | is of distance less than 2 √ δ from 1 -τ is at most 8 √ δk 2 and in particular, there are in expectation no more than a 8 √ δk 2 fraction of clauses for which the following does not hold.

|b 1 | ∈ [1 -τ -2 √ δ, 1 -τ + 2 √ δ]. (12)
We will assume that (12) holds for our clause. Given that µ is almost completely supported on points that satisfy Monarchy, we will first prove a few properties of distributions supported on satisfying points of Monarchy. Lemma 7. For a distribution ν on {-1, 1} k , completely supported on satisfying points of monarchy, i.e. , Pr y∼ν [Monarchy(y

) = 1] = 1, let ∀i b i def = E y∼ν [y i ] . Then, ∀i > 1 b i ≥ -b 1 , (13) 1 k -1 i>1 b i ≥ -b 1 + (1 + b 1 )/(k -1). ( 14
)
Proof: These two properties are linear conditions on the distribution, so if we check them for all points satisfying Monarchy they will follow for every distribution by convexity. They are two types of points in Monarchy -1 (1). There is the point (-1, 1, . . . , 1), and there are points of the form (1, z 2 , . . . , z n ) where not all z i 's are -1. One can check that (13-14) hold for both kinds of points.

We can write our distribution µ as µ = (1 -√ δ)µ 0 + √ δµ 1 where µ 0 is a distribution completely supported on Monarchy -1 (1) and µ 1 is a general distribution on {-1, 1} k . Notice that the biases of µ 0 satisfy the equations ( 13) and ( 14) while the biases of µ 1 do not falsify them with a margin bigger than 2, i.e. the left hand side will be no less than the right hand side minus 2. Lemma 7 then immediately implies that for our µ and b 1 , . . . , b n ,

∀i > 1 b i ≥ -b 1 -2 √ δ, (15) 1 k -1 i>1 b i ≥ -b 1 + (1 + b 1 )/(k -1) -2 √ δ. (16)
We are now ready to prove the following lemma. It essentially shows that the deterministic rounding of the variables with big bias does not interfere with the randomized rounding of the rest of the variables. Lemma 8. For any clause for which the SDP value is at least 1 -√ δ, and b 1 satisfies the range requirement of (12), one of the following happens, 1. x 1 is deterministically set to -1 and all the rest of x i 's are deterministically set to 1.

2. x 1 is deterministically set to 1, and at least two of the other x i 's are not deterministically set to -1.

3.

x 1 is deterministically set to 1, and for some i > 1, b i ≥ 1 -3/2(k -2).

4. x 1 is not set deterministically, and no other x i is deterministically set to -1.

Proof: The proof is by case analysis based on how x 1 is rounded.

First, assume that x 1 is deterministically set to -1. It follows from ( 15) that all the other b i 's are at least -b 1 -2 √ δ so by the assumption in (12) we know that we are in case 1 of the lemma and we are done. Now, assume that x 1 is deterministically set to 1. If for two distinct i's b i > -1 + τ we are in case 2 of the lemma and we are done. Otherwise, assume that b j is the biggest of b i 's, and in particular all other b i 's are at most -1 + τ , we have,

1 k -1 i>1 b i ≥ -b 1 + (1 + b 1 )/(k -1) -2 √ δ by (16) 1 k -1 i>1 b i ≤ b j k -1 + k -2 k -1 (-1 + τ ) by assumption ⇒ b j ≥ -(k -2)b 1 + 1 -2 √ δ(k -1) -(k -2)(-1 + τ ) = 1 -(k -2)(b 1 -1 + τ ) -2 √ δ(k -1) ≥ 1 -(k -2)τ -2 √ δ(k -1) > 1 -1/(k -2) -2 √ δ(k -1) by τ ≤ 1/k 2 ≥ 1 -3/2(k -2) if δ < 1/16(k -1) 2 (k -2) 2 .
This shows that we are in the third case of the lemma and we are done. Finally, assume that x 1 is not deterministically rounded, i.e. , -1

+ τ ≤ b 1 ≤ 1 -τ . It follows from (12) that in fact, b 1 < 1 -τ -2 √ δ. So, one can use (15) to deduce that for all i > 1, b i ≥ -b 1 -2 √ δ > -1 + τ + 2 √ δ -2 √ δ = -1 + τ.
So, we are in case 4 of the lemma and we are done.

We can now look at different cases and show that the parameters and can be set appropriately such that in all the cases the rounded x 1 , . . . , x k satisfy the predicate with probability at least 1/2 + γ for some constant γ. Intuitively, in the first three cases the clause is deterministically rounded and has a high probability of being satisfied, while the fourth case is when the analysis of the clause needs arguments about the absolute values of the biases, and the clause is satisfied with probability slightly above 1/2. We will handle the first three cases first. Define,

C def = Monarchy({1})/ Monarchy({2}) ≈ 2 k-2 . f (b 1 , . . . , b k ) def = 1 Monarchy({2}) k i=1 Monarchy({i})b i = Cb 1 + i>1 b i .
In other words, f (b 1 , . . . , b k ) is the part of (17) that we want to obtain a positive lower bound for, scaled by Monarchy({2}). As Monarchy({2}) is a constant it is then sufficient to lower bound f (b 1 , . . . , b k ).

First, assume b 1 ≤ (2k -4) -3 /2. We know that,

f (b 1 , . . . , b k ) = Cb 1 + i>1 b i ≥ Cb 1 + (k -1)( 1 k -1 i b i ) by concavity of x , ≥ Cb 1 + (k -1)(-b 1 + (1 + b 1 )/(k -1) -4 √ δ) by (16), ≥ Cb 1 + (k -1)(-b 1 + τ /(k -1) -4 √ δ)
as we are in case 4,

≥ Cb 1 + (k -1)(-b 1 + 1/2(k -2) 2 (k -1) -4 δ) by choice of τ , ≥ Cb 1 + (k -1)(-b 1 + 1/4(k -2) 3 -4 √ δ) > Cb 1 + (k -1)(-b 1 + 1/8(k -2) 3 ) assuming δ < 2 -5 (k -2) -6 . Now if b 1 ≥ 0 we are done as f (b 1 , . . . , b k
) would be at least (k -1)(2 k -4) -3 2 -and any constant will do the job. Otherwise, note that the expression inside the parenthesis is at least (2k -4) -3 bigger than b 1 in absolute value. So, if we take to be big enough the second expression is going to dominate the expression. Specifically, first assume

|b 1 | ≥ (4k -8) -3 , f (b 1 , . . . , b k ) > Cb 1 + (k -1)(-b 1 + (2k -4) -3 ) ≥ Cb 1 -b 1 (k -1) + (k -1) b -1 1 (2k -4) -3 = ((C -k + 1)b 1 + (k -1)(2k -4) -3 )b -1 1 ≥ ((C -k + 1)b 1 + (k -1)(2k -4) -3 )(4k -8) -3 +3 as -1 is even > (-(C -k + 1) + (k -1)(2k -4) -3 )(4k -8) -3 +3 , by b 1 < 1 which clearly has a constant lower bound if ≥ (C -k + 1)(2k -4) 3 . Now if |b 1 | < (4k -8) -3 we can write, f (b 1 , . . . , b k ) > Cb 1 + (k -1)(-b 1 + (2k -4) -3 ) > Cb 1 + (k -1)(2k -4) -3 > -C(4k -8) -3 + (k -1)(2k -4) -3 by |b 1 | < (4k -8) -3 = (2k -4) -3 (-C2 -3 + (k -1)), > (2k -4) -3 (k -2), as 3 > log 2 C
which is a constant as long as is some constant. This completes the case of b 1 ≤ (2k -4) 3 /2. Note that so far we have assumed that is some constant and at least max(log 2 C/3, (C -k + 1)(2k -4) 3 ).

Lets assume b 1 > (2k -4) -3 /2. One can write,

f (b 1 , . . . , b k ) = Cb 1 + i>1 b i ≥ Cb 1 + (k -1)(-b 1 -4 √ δ) by (15), = b 1 C -(k -1)(1 + 4 √ δ/b 1 ) > b 1 C -(k -1)(1 + 8(2k -4) 3 √ δ) by b 1 > (2k -4) -3 /2 > b 1 C -(k -1) exp(8(2k -4) 3 √ δ ) by e x > 1 + x ≥ b 1 ≥ (2k -4) -3 2 -,
where to get the last line we have assumed that

δ ≤ (4k -8) -6 -2 (ln(C -1) -ln(k -1)) 2 √ δ ≤ (4k -8) -3 -1 (ln(C -1) -ln(k -1)) 8(2k -4) 3 √ δ ≤ ln(C -1) -ln(k -1) (k -1) exp(8(2k -4) 3 √ δ ) ≤ C -1.
So, as long as C -1 > k -1 we can set = max(log 2 C/3, (C -k + 1)(2k -4) 3 ) and prove that f (b 1 , . . . , b k ) has a constant lower bound depending on k, provided that we assume δ < δ 0 where δ 0 is another function of k. One can check that C > k -2 whenever k > 4. This completes the proof.

We can now finish the proof of Theorem 2. In particular, solve the SDP relaxation of Monarchy, if the objective value is smaller than 1 -δ output a uniformly random solution, and if it is bigger apply the rounding algorithm in Figure 4. In the first case the expected objective of the output is 1/2, while the optimal solution can not have objective value more than 1 -δ, giving rise to approximation ratio 1/2(1 -δ) > (1 + δ)/2. In the second case, at least a (1 -√ δ) fraction of the clauses have objective 1 -√ δ and from these in expectation at least a 1 -16 √ δ(k -2) 2 fraction satisfy (12). We can apply Lemma 9 and Lemma 10 to these. So, the objective function is at least,

(1 - √ δ)(1 -16 √ δ(k -2) 2 )(1/2 + γ) ≥ 1/2 + γ -17 √ δ(k -2) 2 .
This is clearly more than 1/2 + γ/2 for small enough δ, which finishes the proof of the Theorem.

Discussion

We have given algorithms for two cases of MAX CSP(P ) problems not previously known to be approximable. The first case, signs of symmetric quadratic forms, follows from the condition that the low-degree part of the Fourier expansion behaves "roughly" like the predicate in the sense of Theorem 4. The second case, Monarchy, is interesting since it does not satisfy the condition of Theorem 4. As far as we are aware, this is the first example of a predicate which does not satisfy this property but is still approximable. Monarchy is of course only a very special case of Conjecture 1, and we leave the general form open.

Appendix: Proof of Lemma 5

In this section we present the proof Lemma 5 restated here for convenience.

Lemma 5 (restated). For fixed k, define the function ort(ν, Σ) as the orthant probability of the multivariate normal distribution with mean ν and covariance matrix Σ, where ν ∈ R k and Σ k×k is a positive semidefinite matrix. That is, ort(ν, Σ) There exists a global constant Γ that upper bounds all the second partial derivatives of ort() when Σ is close to I. In particular, for all k, there exist κ > 0 and Γ, such that for all i 1 , j 1 , i 2 , j 2 ∈ [k], all vectors ν ∈ R k and all positive definite matrices Σ k×k , (x l -ν l )(x m -ν m )p lm (Σ)/q(Σ)

|I -Σ| ∞ , |ν| ∞ < κ ⇒ ∂ 2 ∂Σ i1j1 ∂Σ i2j2 ort(ν, Σ) < Γ, ∂ 2 ∂Σ i1j1 ∂ν i2 ort(ν, Σ) < Γ,
  ,
where p lm and q are polynomials of degree ≤ k in Σ (depending only on k), and where q(Σ) is bounded away from 0 in a region around Σ. Let y i = x i -ν i . We can then write ∂ 2 ∂Σ ij ∂Σ i j φ(x, ν, Σ) = φ(x, ν, Σ) q(Σ) 4 l,m y l y m (A lm,ij,i j (Σ) + y l y m B lm,ij,i j (Σ))

where A lm,ij,i j and B lm,ij,i j are polynomials depending only on p lm , q, i, j, i and j . Thus, for all Σ in a neighbourhood around I, we have

∂ 2 ∂Σ ij ∂Σ i j φ(x
∂ 2 ∂Σ ij ∂Σ i j ort(ν, Σ) ≤ l,m∈[k] C (2π) k |Σ| +∞ x1=0 • • • +∞ x k =0 1 2 + 3 2 (x l -ν l ) 2 (x m -ν m ) 2 φ(x, ν, Σ) ≤ l,m∈[k] C (2π) k |Σ| +∞ x1=-∞ • • • +∞ x k =-∞ 1 2 + 3 2 (x l -ν l ) 2 (x m -ν m ) 2 φ(x, ν, Σ) = C l,m∈[k] ( 1 2 + 3 2 E x∼N (ν,Σ ) (x l -ν l ) 2 (x m -ν m ) 2 ) = C l,m∈[k] ( 1 2 + 3 2 Σ ll Σ mm + 3Σ 2 lm ) ≤ 19k 2 C,
where we have assumed each element of Σ is at most 2 in absolute value. The cases of partial derivatives with respect to ν i 's follows similarly.

Theorem 11 (Leibniz Integral Rule, see "Differentiation of a Definite Integral." §60 in [START_REF] Woods | Advanced Calculus: A Course Arranged with Special Reference to the Needs of Students of Applied Mathematics[END_REF] ). Consider a real function of two variables f (x, y) and assume that for some x 0 , x 1 , y 0 , y 1 ∈ R both f and ∂ ∂x f are continuous in the region [x 0 , x 1 ] × [y 0 , y 1 ]. Then for any x ∈ (x 0 , x 1 ), d dx

Fig. 1 :

 1 Fig. 1: Standard SDP relaxation of MAX CSP(P ).

Fig. 2 :

 2 Fig. 2: ( , η)-Hyperplane Rounding

Fig. 3 :

 3 Fig. 3: The joint distribution of xi and xj: If g/||g|| 2 is in the thickly drawn arcs then xi = xj.

Fig. 4 :

 4 Fig. 4: Rounding SDP solutions for Monarchy INPUT: "biases" b 1= v 0 • v 1 , . . . , b n = v 0 • v n .

  ∂ 2 ∂ν i1 ∂ν i2 ort(ν, Σ) < Γ.Proof: We know that whenever Σ is a (full rank) positive definite matrix,φ(x, ν, Σ)dx 1 • • • dx k φ(x, ν, Σ) = exp -1 2 (x -ν) Σ -1 (x -ν) [k] (x l -ν l )(x m -ν m )(-1) l+m |Σ ml |/|Σ|  where φ is a normalization of the probability density function of the multivariate normal distribution and Σ ml is the minor of Σ obtained by removing row m and column l. More abstractly, we can writeφ(x, ν, Σ) = exp   l,m∈[k]

  , ν, Σ) ≤ C l,m |y l y m | + y 2 l y 2 m φ(x, ν, Σ) x, ν, Σ)for a constant C (depending only on k). By an iterative application of Leibniz Integral Rule (Theorem 11, below) we can bound the second derivative of ort(ν, Σ) as

f

  (x, y) dy = y1 y0 ∂f (x, y) ∂x dy

(iv) In particular, if δ 2 ≤ δ 2 1 /4(δ 1 -min(s, 0)) 2

(vi) In the notation of[START_REF] Hast | Beating a Random Assignment -Approximating Constraint Satisfaction Problems[END_REF], Monarchy on 4 variables is the predicate 0000000101111111, which is listed as approximable in Table6.6. We remark that this is not surprising since Monarchy in this case is simply a majority in which x 1 serves as a tie-breaker variable.

Lemma 9. If one of the three first cases of Lemma 8 happen for a clause then it is satisfied in the rounded solution with probability at least 1, 1 -(1 + ) 2 /4, and 1/2 + 2 -2 -1 respectively. In particular, if and are constants (only depending on k) and < √ 2 -1 the clause is satisfied with probability at least 1/2 + γ for some constant γ independent of n.

Proof: The first two cases are easy: in the first case the clause is always satisfied by x 1 , . . . , x k while in the second case it is satisfied if and only if at least one i > 1, x i is set to +1. Given that at least two of these x i 's are not deterministically rounded to -1, the clause is unsatisfied with probability at most (1 + ) 2 /4. Now, assume that a clause is in the third case. Then, we know that for some i > 1, b i ≥ 1 -3/2(k -2), so the clause is satisfied with probability at least

, where we have used k ≥ 4.

All that remains is to show that in the fourth case the clause is satisfied with some probability greater than 1/2 and to find the suitable values of and in the process. This is formulated as the next lemma.

Lemma 10. There are constants = (k), = (k), and γ = γ(k), such that, for any small enough δ, any clause for which the fourth case of Lemma 8 holds is satisfied with probability at least 1/2 + γ, if we round with parameters and .

The idea of the proof is to look at such a clause and inspect the objective value of the rounded solution using Fourier analysis. It is not hard to see that for small enough only the linear part of the Fourier expansion of Monarchy (i.e. Monarchy =1 ) "matters". So if we can prove that the linear part of the Fourier expansion contributes something positive we can set small enough and ignore the higher degree part. To do so, we will use (16) to prove that if is chosen big enough, this linear part is dominated by a positive term.

Proof of Lemma 10: We can assume that none of the x i 's are deterministically rounded as being rounded to 1 only helps us. We consider two cases: either b 1 ≤ 0, or b 1 ≥ 0. But first let us write the probability that this clause is satisfied in terms of the Fourier coefficients.

So all we have to do is to find a value of and a positive lower bound for k i=1 Monarchy({i})b i that holds for all valid b i 's. It is easy to see that

A further interesting special case of the conjecture is a generalization of Monarchy called "republic", defined as sign( k 2 x 1 + k i=2 x i ). In this case the x 1 variable needs to get a 1/4 fraction of the other variables on its side. We do not even know how to handle this seemingly innocuous example.

It is interesting that the condition on P for our ( , η)-rounding to succeed turned out to be precisely the same as the condition previously found by Hast [START_REF] Hast | Beating a Random Assignment -Approximating Constraint Satisfaction Problems[END_REF], with a completely different algorithm. It would be interesting to know whether this is a coincidence or there is a larger picture that we can not yet see.

As we mentioned in the introduction, there are very few results which give approximation algorithms for large classes of predicates, and it would be very interesting if new such algorithms could be devised.