Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems
Authors: Vincent Cohen-Addad
Tommaso d'Orsi
Anupam Gupta
Euiwoong Lee
Debmalya Panigrahi
Venue: NeurIPS 2024 poster (2024)
Keywords: learning-augmented algorithm
approximation algorithm
maximization
CSPs
learning with advice
Primary area: optimization
TL;DR: This paper presents learning-augmented algorithms for maximum cut and other max-CSPs.

Abstract: In recent years, there has been a surge of interest in the use of machine-learned predictions to bypass worst-case lower bounds for classical problems in combinatorial optimization. So far, the focus has mostly been on online algorithms, where information-theoretic barriers are overcome using predictions about the unknown future. In this paper, we consider the complementary question of using learned information to overcome computational barriers in the form of approximation hardness of polynomial-time algorithms for NP-hard (offline) problems. We show that noisy predictions about the optimal solution can be used to break classical hardness results for maximization problems such as the max-cut problem and more generally, maximization versions of constraint satisfaction problems (CSPs).

Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems
Vincent Cohen-Addad
Tommaso d'Orsi* Bocconi University
Anupam Gupta
Google Research
New York University New York NY 10012
France
Italy
coheaddad@google.com com
commass..orrae Swsrrssinibboocoo.... it
anupam.. g@nyu edu
Euiwoong Lee
Debmalya Panigrahi
University of Michigan Ann Arbor MI 48105 euiwoong@umico ch. edu
Duke University
Durham NC 27708
debmalya@cs duke edu
Abstract
In recent years, there has been a surge of interest in the use of machine-learned predictions bypass worst-case lower bounds for classical problems in combina- torial optimization. So far, the focus has mostly been online algorithms, where information-theont barriers are overcome using predictions about the unknown future. In this paper, we consider the complementary question of using learned information to overcome computational barriers in the form of approximation hardness of polynomial-time algorithms for NP-hard (offline) problems. We show that noisy predictions about the optimal solution can used to break classical hardness results for maximization problems such as the max-cut problem and more generally, maximization versions of constraint satisfaction problems (CSPs).
Introduction
The design and analysis of algorithms beyond the classical worst-case paradigm has been an active area of research (see, e.g., the collection of surveys by Roughgarden (2020). ). In recent years, this has been accelerated by the success and widespread adoption of machine learning models across application domains, leading researchers to ask: can use muchine-learren information typical instances of a problem better than what we can hope for in the worst case? This meta-question has been particularly influential in the realm of online optimization, where the goal is design algorithms for inputs that are revealed sequentially over time. Indeed, assuming that the future unfolds in typical rather than worst-case manner, algorithm with predictions learned based on past data, thereby helping bypass information-theoree lower bounds. This principle has been successfully applied to broad range of online problems, such as caching [Lykouris and Vissilvitskii 2021]. rent-or-buy [Purohit et al. (018). covering [Bamas] al. (020b)), network design Azar [002 and many others (see related work for more references).
solve
compensate for the information deficit of the online
[2022] scheduling Azar al. [202]] matching Dinitz et al.
In this paper, we study the role of machine-learned predictions in offine NP-hard problems. For offline problems, an algorithm has no information disadvantage compared to an optimal solution: the visadvantage is computational. The NP uP-hardness of problems makes exact algorithms that run in polynomial time unlikely. This has led the field of approximation algorithms, where the goal to obtain polynomial-time algorithms that output solutions that are approximately optimal. In
Part of this work was done the author was at Zurich. Part of this work was done when the author was at Carnegie Mellon University.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

particular, an approximation algorithm for an optimization problem has an approximation factor of if the solution it produces on every instance is within a factor of of that of an optimal solution. The best approximation factor for an NP-hard offiin problem is also subject to computational barriers. For instance, for the classical MAXCUT problem, it is known that the approximation factor of aGW R 0.878 obtained in the celebrated work of Goemans and Williamson (1995] is the best possible under the Unique Games Conjecture (UGC). This raises a natural question: can we use machine-learner predictions to overcome computational barriers to approximation algorithms for NP-hard problems?
1.1 Our Contributions
Suppose we are given a noisy prediction that is mildly correlated with an optimal solution for a given problem instance. Can solution than is possible without any prediction? For (strongly) NP-hard problems, we typically know barriers for the best approximation factor a that can be achieved by polynomial-time algorithms. Using a machine-learned prediction of an optimal solution, we seek to go beyond this barrier: to obtain a polynomial-timee algorithm with an approximation factor strictly better than a. The quantum of improvement naturally depends on the quality of the prediction: if the prediction is e-correlated with the target solution, can we get an a + (e) approximation?
such a prediction recover a better approximation to the optimal
To make these questions concrete, we first consider the MAXCUT problem in the learning- -aggmente setting. Given an undirected, weighted graph, the MAXCUT problem asks for a bi- partition of the vertices such that the total weight of edges in the cut is maximized. Assuming the accepted unique games conjecture, the Goemans- Williamson approximation bound of oow R 0.878 is the best possible for polynomial-tine max-cut that is independently correct for every vertex with probability 1/2 + E, for any E >> O. (Note that random guessing achieves correctness of 1/2; so, we assume that the prediction is only s-better than random guesses.) Can this prediction be used to obtain an approximation factor better than OGwW in polynomial time? This question was posed by Svensson in his SODA 2023 plenary lecture.
algorithm. But, suppose we given a prediction for the optimal
Our first result is to unconditionally improve on worst-case performance for the MAXCUT problem using an e-correlated prediction. This answers the question posed by Svensson in the affirmative. Specifically, we give an algorithm that obtains an (OGw + "(e="))apprrximall MAXCUT solution. This also quantifies the dependence between the improvement in the approximation factor and the correlation of the prediction with the actual optimal solution. Interestingly, we also relax the independence requirement to just pairwise independence of the predictions the vertices. This is significant because in practice, the predictions for the different vertices are likely to be obtained human expert, either of which sources are unlikely to output
from machine learning model completely independent predictions for different vertices.
We further complement this result by considering another natural prediction model where instead of a noisy prediction for every vertex, we get correct prediction but only for an e e-fraction of randomly chosen vertices. (To distinguish between these models, we call the former noisy predictions and the latter partial predictions.) In this case, we obtain an (OgT + ((e))--pproximate solution to MAXCUT, where OgT ~ 0.858 is the approximation factor obtained by Raghavendra and Tan for the MAXBISECTION problem (Raghavendra and Tan 2012). Note that orT is slightly smaller than aGw. but we get a better advantage of (?(s) instead of ()=
Next, show that our algorithmic framework is applicable beyond the MAXCUT problem. Con- straint Satisfaction Problems (CSPs) are a broad class of optimization problems that includes fundamental optimization tasks such as MAX-k-SAN MAX-K-LIN, MAX-K-AND, etc. In particular, 2-CSPs are a subclass of CSPs where each constraint contains only two variables. This includes problems such as MAXCUT, MAXDICUT, and MAX-2-SAT. classical result of Arora et al. (9999 showed that it is possible to obtain an approximation factor arbitrarily close to 1 for "dense" instances of all 2-CSPs including MAXCUT. We show that e-correlated predictions of the optimal solution is a useful tool for dense instances of all 2-CSPs. In particular, we use the prediction to lower the "density threshold" for obtaining an arbitrarily small approximation factor for dense instances of 2-CSPs. In other words, the assumption on the density of the instance (which is function of the prediction bias and the approximation error) for our result the Carning-augmente setting weaker than that of Arora et al. [1999] i.c., our result applies to broader set of instances.

---

1.2 Related Work
In recent years, the abundance of data and the tremendous success of machine learning has led to a variety of attempts at going beyond traditional worst-case analysis for combinatorial optimization by taking advantage of learned information.
clustering, (Ashtiani et al. [0T6]] introduced a setting where an algorithm can query an external oracle (e.g., machine learning model) to learn if pair of points are in the same cluster in the optimal clustering (same-cluster queries). The goal then is to recover optimal solution (or sufficiently good approximation) while minimizing the number of oracle queries. Tight bounds have been obtained for various clustering objectives in this setting, from k-means (Ailon et al. [0188] to correlation clustering [Mazumdar and Saha 2017]. Moreover, robust settings that incorporate noise in the oracle answers have also been studied Larsen et al. 2020],
Del Pia et al. [2022]. J. Another line of work Ergun al. [2022] Gamlath et al. [2022] considers k-means and related clustering problems where the algorithm is provided noisy node labels. For
instance, Gamlath et al. [2022] showed that even when the labels provided by the oracle are correct
with a tiny probability (say 1%), it is possible to obtain a (1 + apprrxipppiiiiitionn to the k-means
objective as long as the clusters are not too small.
different line of work has aimed to incorporate machine-learner predictions in the design of online algorithms (see, e.g., the surveys Mitzenmacher and Vassilvitskii (2020) (0222). This model was introduced by Lykouris and Vassilvitski for the caching problem Lykouris and Vassilvitskii [202]]
and has since been studied in many problem domains such rent buy Purohit et al. [2018]
Gollapudi and Panigrahi [2019), Anand et al. [2020). covering Bamas et al. [2020b] Anand et al.
[2022] Gupta et al. [2022]. scheduling Purohit et al. [2018). /Wei and Zhang [2020] Bamas et al.
2020a Lattanzi et al. 2020). Mitzenmacher [2020]. Azar et [2221],Coohe and Panigrahi [023
Lindermayr al. [2023] Lassota al. [2023). caching Lykouris and Vassilvitskii [2021], Wei 2020
Jiang et al. [2022b], |aansal et al. [2022]. matching Dinitz et al. [2021]. Lavastida et al. [021
secretary problems Antoniadis al. [2020b] Dütting et 2202 J. graph problems Antoniadis et al.
[2020a]. Jiang et al. Almanza et al. [2021]. Antoniadis et al. [2023]. Bernardini et al. [2022].
Almanza
Anand et al. 2022). Fotakis al. 2021 J Azar al. [2022], and many others. (The reader referred
10 AAP [023]] for a compendium of papers in this area.) The main goal in this line of work is to overcome information-theoree lower bounds for online problems using machine-learned predictions about the unknown future.
Two recent works (concurrent and independent of ours) have considered the computational complexity of MAXCUT and CSPs in the context of noisy predictions. The first of these is |ampis et al. 2024]] who tackle the problem of speeding up approximation schemes for dense CSP instances using noisy predictions. Namely, they provide an algorithm that achieves a (1 - e) approximation whose running time depends on the density of the instance and the error in the prediction. The algorithm runs in polynomial time if the number of edges in the instance is 22(n2/ / log r)), assuming the prediction label of each vertex is correct with constant probability. The second work is by Ghoshal et al. [2024), who consider both the partial and the noisy predictions models under full independence of the predictions. -
They provide ((((OV(EV ()ppooiiioooi for both models, where A is the average degree of the graph. Alternatively, they show that if the edges are weighted, the value of the solution computed is at least opt. vn Eng w
2 Preliminaries
The MAXCUT Problem. We start by describing the MAXCUT problem. In this problem, we are given a weighted graph G
(V, -V,V, E) represented by (symmetric) n n adjacency matrix A, where Ag Wig, the weight of edge [i,j] if it exists, and 0 otherwise. (We assume the graph has no self-loops, and hence A has zeroes on the diagonal.) We let W; = E, Wij denote the weighted degree of vertex i. We use D == diag WW...., Wn,) to denote the diagonal matrix with these weighted degrees, and L = D - A to denote the (unnormalized) Laplacian matrix of the graph. Note that x E (-1, 1)" denotes a cut in the graph, and the quadratic form (r, Lx) = Et Wiy(r; - 22)²
counts (four times) the weight of edges crossing the cut between the vertices labeled 1, and those labeled -1.
3

---

The MAXCUT problem asks for the cut with maximum edge weight. Hence, MAXCUT can be rephrased as follows:
MAXCUT(G) := max 1/4 (z. Lz). =
We defer the formal definition of CSPs to Section 5
The Noisy/Partial Predictions Framework. We describe the prediction models for the MAXCUT problem. We extend the noisy predictions model to general Max-2-CSPs in Section
1. In the noisy predictions model for MAXCUT, we assume there is some fixed and un- known optimal solution x² [-1,1]". The algorithm has access to prediction vector Y E {-1,1}", such that for each vertex i, Y, is the correct label z; with some (unknown) probability 1/2 + E, and is the other (incorrect) label with probabil- ity 1/2 - 8. Here we only assume pairwise independence; for any two vertices i and j. Pr[i,j both give their correct labels] = (1/2 + e)².
2. In the partial predictions model for MAXCUT, the algorithm has access to a prediction vector Y E f,,1,0,17 13" such that for each vertex i, Y, is the correct label xu with some (unknown) probability E and is 0 otherwise. Again, we only assume pairwise independence; for any two vertices i and j. Pr[i, j both give their correct labels] =
3 MAXCUT in the Noisy Prediction Model
Recall that in the noisy prediction model, the predicted label of each vertex its correct label in a fixed max-cut with probability 1/2 + e. Moreover, the labels are pairwise independent. One can show that in this model, if one were simply output the prediction itself, then its value would be at least (m/2 + E² (opt- m/2)) for an unweighted graphs with m edges. But, this is generally worse than the øGw opt 0.878 opt bound obtained by the Goemans Williamson Goemans-Williamson MAXCUT algorithm. Our main result is to give algorithm that uses noisy prediction to outperform Ogw in the approximation bound by an additive poly(e) factor:
Theorem 3.1 (Noisy Predictions). Given noisy predictions with a bias of there is a polynomial -tmme randomized algorithm that obtains an approximation factor of agw + (2((a) in expectation for the MAXCUT problem.
The rest of this section is devoted to proving the above theorem. A basic distinction that will use throughout this section is that of A-wide and A-narrow graphs; these should be thought of as weighted analogs of high-degree and low-degree graphs. We first define these and related concepts below, then we present an algorithm for the MAXCUT problem on A-wide graphs in $3.1 followed by the result for nanarrow graphs in $32
We finally wrap up with the proof of Theorem 3.1
We partition the edges incident to vertex into two sets: the A-prefxx for comprises the A heaviest edges incident (breaking ties arbitrarily), while the remaining edges make up the A A-suffix for i. We fix a parameter E (0, 1/2). We will eventually set A = (11/s²) and v) to be an absolute constant. Recall that W.- Σje(n) Aij is the weighted degree of
Definition 3.2 (A (A-Narrow/Wide Vertex). A vertex i is A-wide if the total weight of edges in its A-prefix is at most nW, and so the weight of edges in A-suffix is at least (1-1) Otherwise, the vertex is A-narrow
Intuitively, a A-wide vertex is one where most of its weighted degree is preserved even if we ignore the heaviest edges incident to the vertex.
We partition the vertices V [n] into the A-wide and A A-narrow sets; these are respectively denoted VA and Vea. We define W> := Eievs W, and Wea := =iivesa W., and hence the sum of weighted degrees of all vertices is W := Σ W, = W>A + W<A.
Definition 3.3 (A-Narrow/Wide Graph). A graph is A-wide if the sum of weighted degrees of A-wide vertices accounts for at least - -nffraction of that of all vertices; iee, if > A 2 W1. Otherwise, is A --narrow.

---

3.1 Solving MAXCUT for w-wide graphs
For A-wide graphs, show:
Theorem 3.4. Fix e' E (0,1). Given noisy predictions with bias there is a polynomial-tine randomized algorithm that, given any A-wide graph, outputs a cut of value at least the maximum cut minus (5n 2,')W, where A O(1/(E ) with probability 0.98.
Since the graph is A-wide, most vertices have their weight spread over a large number of their neighbors. In this case, the prediction vector allows us obtain good estimate é of the optimal neighborhood imbalance r" (the difference between the number of neighbors a vertex has on its side versus the other side of the optimal cut). We can then write an LP assign fractional labels to vertices that maximize the cut value while remaining faithful to these estimates r;; finally rounding the LP gives the solution.
3.1.1 The A-wide Algorithm
Define an X n matrix Å from the adjacency matrix A as follows: for each row corresponding the edges incident to vertex i, we set the entry Å. 0 if the edge ji is in the A A-prefix of vertex i; otherwise, Acj Aej. Now, define an n-dimensional vector f as follows:
25 (AY), 0
i A-id is A-narrow
A
where Y is the prediction vector. Solve the linear program:
min (f,z) s.l. || Axll1 S (e' 21)W
(1)
=E[-1.1]"
Let [-,,
1] be the optimal LP solution.
Finally, do the following (1/x)) times independently, and output the best cut X among them: randomly round the fractional solution á independently for each vertex to get cut X E 1-1, namely, Pr[X, = 1] (1+2:)/2 and Pr[X; = -1] (1-2:1/2.
3.1.2 The Analysis
For labeling E 11", the neighborhood imbalance for vertex i is defined as Σ3 Ayæz = (Ax); This denotes the (signed) difference between the total weight of edges incident to i that appear and do not appear in the cut defined by the labeling æ. The maximality of the optimal cut S 0 for all i; else, switching from 1 to -1 or
xx E 1] ensures that xt sign((Ax") vice-versa increases the objective. Define r* == Ar as the vector of imbalances for the optimal cut.
Lemma 3.5. The vector satisfies
n
W
f|lf 111]
E
ril
S
0
WnW.
VVV
Proof. Observe that
E|y] x. Pr[Y; x;J] -x: Pr(y; x;²] = xz (1/2 - x1/2 6) = -2.r.-
Define Z = 2 Y. Then, E|[ = and so [|AZ]] -
First, we consider A-narrow vertex i. Since f: 0, we have over all A-narrow vertices gives
1 = |n2l S W. So summing
Σ NEVC
W Σ
W, S w,
(2)
VEVRA
since the graph is A-wide.
Now, we consider A-wide vertex i. We have
|rz r (ĀZ): r²l [B((ÁZ)) - ((AZ)) -E(AZ))]]
(3)
5

---

To bound the first term in the RHS of G3, recall that r = B[(AZ):] Thus,
[B(())).] - - - -((A2))))(( ((Á A)i, B(1))
Since B = x² - 11,, we get
-ra1 x II A) S,
where in the last step, we used the fact that i is A-wide vertex.
Now, bound the second term in the RHS of Using Chebyshev's inequality the (AZ); Ej Aij Zz. get
- [[((A))]I X.] var( (AZ)))
X
Since the variables 2j are pairwise independent, the variance var var((AZ);) = E, Ab, var(Zz). The variance each Z, O(1/E²). For Σ; A. we know
Σ JEin]
B2 11,11 = |1ll 1|A:
Note that the weight of any edge in the A-suffix of is at most W,/A Therefore, by our definition of A, we have || I W. Since A.j I Ai for all E [n], we also have ||A S ||A| = W.. Applying these bounds, get: jee(n) Abj I W/? A.. Therefore,
E| (AZ), (((A))ll) 3 = s O(Ws/(eVA)).
Summing over all A-wide vertices, we get
5o WsA LVVA
W
A ril
+ tn
+ n,W.
VEV
Combining with for A-narrow vertices, get
W
E [i r 1hh)
+ 2n/WW
EVA
Now using Markov's inequality with Lemma 3.5 we get that setting A = ((1/((EE))) for any fixed constant è ensures that we get vector of empirical imbalances f satisfying
||f - r S (E' 2.)
(4)
with probability at least 0.99. (Since the 2nW losses are deterministically bounded, we can use Markov's inequality only on the random variable Liev, (ÁA), [[(ÁZ)]]]) Hence, when the event in (4) happens, the vector x² is feasible solution to LP !
Next, we need to analyze the quality of the cut produced by randomly rounding the solution of LP (1. Recall that for the (unnormalized) Laplacian 7. and some 11 the cut value
fxx 1/4- (x, Lœ) 1/4- ((x, Dr) (x, Az)) 1/4 (W (ax, Az)).
(5)
Lemma 3.6. For any A-wide graph, the algorithmmfron 331.11 outputs X E (-1,1)" that satisfies
f(X*) 2 f(x*) (2e' + W
with probability at least 0.98.
Proof. Recall that the cut X* is the best among T = 0(1/)) independent roundings of cut f.
Consider one of the roundings X, and write:
AX (ū, f) + ((ē, Aa) (é, f)) ((X, AX) -(ē, A&:)).
(6)
Let us first bound the expectation of each of the terms in the RHS of (6) separately.

---

To bound the first term (á, f). note that given 44) (which happens with probability 0.99), the solution x² feasible for the LP This means the optimal solution & has objective function value
() S (f, (r" x²) ) (f-r" ,-) S (x", AAxxxx)>>> + I|F r" ||=||æ* 11o0
(x" Ax") + (c' W.
Next, we bound the second term ((t, Aτ) (i) by
| |i - Fll1 S (s' + W,)
(8)
by feasibility of á for the LP ( Finally, we bound the third term ((X,AX) - (Ø, Ai)), this time in expectation:
E (X, AX)] - (i., A.. = 0.
(9)
Chaining eqs. (7) to for the various parts of (6). we get
[X AX) - (z" Ax") + (2e' + 4n)
Moreover, using that (X, AX) E [- W). we get
Pr [[X AX)
B X w/] Pr (XX W EKX AX) + (1 W)
$ Pr [X, AX) W 2 (1+ n/2) (El AX)] + W))
I 1/L+n/2)).
If X is the cut with the smallest value of (X, among all the independent roundings:
Pr [X", AX") (x" Arr) (2e' W] 2 (4/4+/22)) 2 0.99.
Substituting into the definition of f()) completes the proof.
This proves Lemma 3.6. and hence also Theorem 3.4
Deterministic Rounding. We observe that we can replace the repetition by simple pipeage rounding algorithm to round the fractional solution & to an integer solution X without suffering any additional loss. Indeed, viewing (a,, Ax) as a function of some x; keeping the remaining (. Jn \ {œx] fixed gives us linear function of x; (since the diagonals of A are zero). Hence we can increase or decrease the value of x; to decrease (ær Ar) until x; 1). Iterating over the variables gives the result. However, this does not change the result qualitatively.
3.2 Solving MAX CUT for A-narrow graphs
Next, consider A-narrow graphs. We show:
Theorem 3.7. For any A E N, there is randomized ulgorithm for the MAXCUT problem with an (expected) approximation factor of (kGW 22112/ /2) any A-narrow graph.
For the case of A-narrow graphs, we do not use predictions: rather, we adapt an existing algorithm for the MAXCUT problem for low-degree graphs by Feige et al. [2002) and its refinement due to Hsieh and Kothari 2022]. Note that any graph with maximum degree A is clearly A-narrow (even when 1) 1).
3.2.1 The A-narrow Algorithm
We show that Theorem 3.7 holds for the Feige, Karpinski, and Langberg (FKL) MAXCUT algo- rithm [Feige et al. [002]. We briefly recall this algorithm first. Consider the MAXCUT SDP with triangle inequalities:
(1 (1,, Uz)
max w.S. viE(n) ||a.;
Σ
A
2
K<)E)) mg]
s.t.
bu libo; cuxll3 2 ||ar; coa Vi,j. k inl, 1-1,
where Sn is the unit sphere of dimensions. Let 0 be an optimal solution to this SDP.
7

---

Let be random vector where each coordinate is sampled independently from a standard normal distribution. We use random hyperplane rounding from the MAXCUT algorithm of Goemans and Williamson 1995 to round e to 1 E {-1,1)" as follows: if (0:: > 0, then .; = 1; else, 2i = -1
Now, define F = {i E [n| (ū; g) E [- [, o]} for some 5 = @ ( ( /lo (n)())))), We
partition N; := [n]] (i) as follows: B; {j E NAF: ... ). and C; == {j E E F F 2
and D: = N; n F. We define F" [ F as follows: i E P" if E F and w(B:) > w(C,) + (D:) where (S
Ejes Aij. In the final output X E (-1,1)% we flip the vertices in F", namely
X; -;; if i F", else X; 24
We now give an analysis for the FKL algorithm establishing Theorem 3.7
The "local gain" for a vertex i E F is defined as A; : (B,, (DP + ICa)) where 2t max(z, 0). We now state the following key lemmas:
Lemma 3.8. For any vertex E [n]. Pr(i F] = (())
Proof. This lemma immediately follows from [Hsich and Kothari 2022 Fact 3].
Let be a A-narrow vertex, and E R" be its weight vector (w; Aij for all j [n]) so that W; = I|wi]l Let w' E R" be the projection of w onto its top A coordinates. The narrowness of i implies that w 1I1 s/]lu|1,, which implies that
IIl A
1/111 A
|
>
|
It turns that the analysis of Hsieh and Kothari 2022
still holds under the above bound between l and l norms of weight vectors. So we have the following slight generalization of their Lemma 8. Lemma 3.9 (extends Lemma 8 Hsieh and Kothari (2022). There is a large enough constant C such that for any d 2 3 and = Cdwlogd for any vertex whose weight vector w satisfies ||ll| s d||w]|| [2 it holds that the expected local gain of a vertex i satisfies:
W;
E[A|iEF] =
dy/log
Proof. In Hsieh and Kothari (2022) the only place where the degree bound d is used is || < dl 2 at the end of the proof of Lemma 7.
Proof of Theorem 3.7
Note that the value of the cut X exceeds that of & by EieFy i,.ic.
E (X, LX)] [( Lay] +
Σ E|A E FJ PPrji E F)
(E(M)
2 Fl La)
+
Σ
E[A F) Pr(i F).
na-narrow
Let the approximation factor of the cut è output by the Goemans- algorithm be denoted OGW and let opt be the size of the maximum cut. Then,
[2 L 2 aGW opt.
From Lemmas 3.8 and 3.9 with d A/12, get
[[((, LX)] 2 aGW - -pt +
Σ
W (A/12) log A/n²)
(A/1²) A/T2)
A :A-narrow
Since En W, 2 n/W 2 2ny opt, we get
B[X, LX) 2 (aow + 0((7/A2)) opt.
3.3 Wrapping up: Proof of Theorem 3.1
For A-wide graphs, Theorem 3.4 returns cut with value at least opt - (2n + e' with probability 0.98. Since we can always find cut of value ogw opt, and opt 2 W/2, this means the expected cut value is at least [0.98 (1 - Grz - 2s') + 0.02 agw opt. And for A-narrow graphs. Theorem 3.7 finds cut with expected value [aow + [A?]] opt. Moreover, recall that A O(1/(EE'))) Setting n, e' to be suitably small universal constants gives us that both the above approximation factors are at least agw + )))=)) which proves Theorem 3.1
8

---

MaxCut in the Partial Prediction Model
We now consider the partial prediction model, where each vertex correct label with probability& e. Intuitively, this prediction model provides more information than the noisy prediction model since all predictions are guaranteed be correct. Indeed, this is reflected in out first bound: we show that since an E² fraction of the edges are induced by the vertices with the given labels, it is easy get an approximation ratio of almost aGw + (?=²). (We give details in Appendix A
reveals their
Theorem 4.1. Given noisy predictions with a rate of E, there a polynomial -imee randomized algorithu that obtains (expected) approximation factor of acw + E² for the MAXCUT problem
Although the (ee²)) advantage in this theorem is already better than (ss= in Theorem 3.1 we ask if can we even better given the more informative predictions. Ideally, we could get an (2[e -adaanadae if the hyperplane rounding performs better than agw for the edges with only one endpoint's 's label revealed, One naive way to achieve this is to hope that the rounding preserves the marginals; i.c., B[r,] (vo, v1) for all i E [n]. In that case, if we consider (i.j) where if 2y Ioo the probability that () is cut is exactly their contribution to the SDP (1 (0%, my))-
Since the hyperplane rounding does not satisfy this property, we use the rounding scheme developed by |Raghavendra and Tan [2012] for max-bisection that has an approximation ratio oRT 0.858 while preserving the marginals. The proof of this theorem is deferred to Appendix A.
Theorem 4.2 (Partial Predictions). Given partial predictions with a rate of E, there is a polynomial- time randomized algorithm that obtains an (expected) approximation factor Our + (1 OgT (2 - =²) for the MAXCUT problem.
2-CSPs in the Noisy Prediction Model
In this section, we go beyond the MAXCUT problem and consider general 2-CSPs. In particular, extend Theorem 3.4to this broader class of problems. Let us first define Max-2-CSPs (Constraint Satisfaction Problems). Each constraint is predicate on two variables: e.g., AND, OR, Not-Equals, or Xor. We are given a collection of such constraints (each on two variables), and the goal is to find an binary assignment to the variables that satisfy the maximum number of constraints. (E.g.. the predicate is Not-Equals, and constraints form the edges of some graph, we get the MAXCUT problem.)
Formally, for multi-index a E [n]] we denote by (()) its i-th index and by x the pair (Ia Fa (2)). For variables 21, Fn, then write (x( for the monomial II z;- Given predicate P
(-1,+1)2 {), instance I of the CSP(P) problem over variables :1;---, Fr is multi-set of triplets (w, c, a)) representing constraints of the form ((c1)a(1), (2 = 1 where a E [n]² is the scope, E {11 is the negation pattern and w 2 0 is the weight of the constraint. For brevity we often write (cco x²) place of ((c1)a(1)) (2)) We let W Σ (( (w.e, w. We can represent the predicate P as the multilinear polynomial of degree in indeterminates Po(1);Fa(22)
P(coz = Σ ád p(a') (x),
aCCa
where p(a') is the coefficient in P of the monomial Xa (x). Notice that this formulation does not rule out predicates with the same multi-index but different negation patterns or multi-indices in which an index appears multiple times. Given predicate P, an instance I of CSP(P) with m constraints and x E (+1}", we define
valz(x) = W
1
w De-P(co''' x (w.C.)EE
Σ
and opt == max valz(z). #6(+1)"
For instance, MAXCUT on graph G ([n]. E) can be captured in this framework where P(x, y) (1 22) each edge (i.j) [n] yields triplet a, where 1, c (1, 1) and a (i. In the noisy prediction model for CSPs, for an instance I of CSP(P), we assume there is some fixed assigment x² with value valz(x*) optz The algorithm has access prediction vector

---

YE E {+1]" such that predictions V/ 's are 2-wise independently correct with probability 1+s for unknown bias e. We let Z y
2 2: With slight abuse of notation also write P(c za) even though a rescaled boolean vector.
For a literal i E [n] and an instance I of CSP(P) we let S; == {(w, c, a) E Z a((1) = if As in Sectioon 3.1.1] we can define A-wide literals and instances. For an instance I, we partition the constraints in S; into two sets: the -rerfx for i comprises the A heaviest constraints in S; (breaking ties arbitrarily), while the remaining constraints make up the A --sufix for i, which we denote by S, We fix a parameter 77 E (0, 1/2). We let W, L(w,ca))ss W/.
Definition 5.1 (A-Narrow/Wide), A literal i is A A-wide the total weight of its in its --prefix is at most n and so the weight of edges its A-suffix is at least (1 n, Otherwise, the literal i is A-narrow. An instance I of CSP(P) is A-wide if 2 iE[n]
W; 2 (1 n)
A-wide
We are now ready state the main theorem of the section.
Theorem 5.2. Let P [+1]² - 10 be predicate. Let e' E (0.1), E (0,1/2) and 2 0(1/(e' - e)²). There exists a polynomial-time randomized algorithm that, given a A-wide I in CSP(P) and noisy predictions with bias e, returns vector & E {+1)² satisfying
valz(x) 2 optz 5n O
with probability at least 0.98.
The proof of Theorem 5.2 follows closely that of Theorem 3.4 and is deferred to Appendix B.2
6 Closing Remarks
Our work suggests many directions for future research. One immediate question is to quantitatively improve the exponent of & for noisy predictions, and the constants. Here are some broader questions:
1. We assume that our noisy predictions are correct with probability equal to 1/2 + E; we can easily extend to the case where each node has a prediction that is correct with some probability 1/2 + E;, and each 6; E ((s). Can we extend to the case when we are only guaranteed E 2 for every i?
2. For which other problems using noisy predictions? As we showed, the ideas used for the A-wide case extend to more general maxinization problems on 2-CSPs with "high degree". but can we extend the results for the "low-degree" case where each variable does not have a high-enough degree to infer a clear signal? Can we extend these to minimization versions of 2-CSPs?
improve the performance of the tfate-ofthhe-ee algorithms
3. What general lower bounds can we give for our prediction models? We feel that agw + +O()) is natural barrier. One "evidence" we have is the following integrality gap for the SDP used in the partial information model; starting from gap instance and an SDP solution exhibiting opt & OcW sdp for the standard SDP (without incorporating revealed information), given labels for en vertices, our new SDP simply fixes the positions of the corresponding en vectors, but doing that from the given SDP solution decreases the SDP value by at most (()) in expectation, which still yields opt S (acw O(s))sdp. (Note that you replace the SDP gap with any hypothetical gap instance for stronger relaxations.)
Given that the partial predictions model is easier than the noisy predictions model and our entire algorithm for the partial model is based on this SDP, this might be considered as a convincing lower bound, but it would be nicer to have more general lower bounds against all polynomial-time algorithms.
4. Our models only assume pairwise independence between vertices: can we extend our results to other ways of modeling correlations between the predictions? In addition to stochastic predictions, can we incorporate geometric predictions (e.g.. in random graph models where the probability of edges depend on the proximity of the nodes)?
10

---

Acknowledgments
We thank Ola Svensson for enjoyable discussions. AG was supported part by NSF awards CCF-2006953 and CCF-2224718, and by Google, Inc. EL was supported in part by NSF award CCF-2236669 and by Google, Inc. DP was supported in part by NSF awards CCF- 1955703 and CCF-2329230, and by Google, Inc.
References
Online index for algorithms with predictions, 2023, https://algorithhme with htt.p/prrttto----tb--rrrrreiiooi github.io/
Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Approximate clustering with same-cluster queries. In Anna Karlin, editor, 9th Innovations Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA. volume 94 of LIPlcs, pages 40:1-40:21, Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2018.
Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6- 6-14, 2021, virtual, pages 4661-4673, 2021.
Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ML predictions for online algorithms. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 303-313. PMLR, 2020.
Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. In Kamalika Chaudburi, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 598. PMLR, 2022.
Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 345-355, PMLR, 2020a.
Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florine Balcan, and Hsuan- Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020b.
Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Mixing predictions for online metric algorithms. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICMI. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 969-983. PMLR, 2023.
Sanjeev Arora, David R. Karger, and Marek Karpinski. Polynomial time approximation schemess for dense instances of np-hard problems. J. Comput. Syst. Sci., 1811):13--210 1999.
Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. Advances in neural information processing systems, 29, 2016.
Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, I, pages 1070-1080. ACM, 2021.
11

---

Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9- /2, 2022, pages 35-66. SIAM, 2022.
Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020a.
Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning aug- mented algorithms. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020b.
Evripidis Bampis, Bruno Escoffier, and Michalis Xefteris. Parsimonious Garming-augmentt approx- imations for dense instances of N'P-hard problems, 2024.
Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. Learning-augmented weighted paging. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 12, 2022, pages 67-89, SIAM, 2022.
Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti- Marchetii-Spaccamlla Nicole Megow, Leen Stougie, and Michelle Sweering. A universal error measure for input predictions applied to online graph problems. In Sanmi Koyejo. S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors. Advances in Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA. USA, November 28- December 9, 2022, 2022.
Ilan Reuven Cohen and Debmalya Panigrahi. general framework for learning- augmented online allocation. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Pader- born, Germany, volume 261 of L.Plcss pages 43:1-43:21. Schloss Dagstuhl Leibniz-7entrum für Informatik, 2023.
Schloss
Alberto Del Pia, Mingehen Ma, and Christos Tzamos. Clustering with queries under noise. In Conference on Learning Theory, pages 5278-5313. PMLR, 2022.
Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 10393-10406, 2021.
Paul Dütting, Silvio I Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In Péter Biró, Shuchi Chawla, and Federico Echenique, editors, EC '21: The 22nd ACM Conference Economics and Computation, Budapest, Hungary, July 18-23, 2021, pages 409-429. ACM, 2021.
Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning-augmented Sk$-means clustering. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
Uriel Feige, Marek Karpinski, and Michael Langberg. Improved approximation of max-cut on graphs of bounded degree. J. Algorithms, 43(2):201-219 2002.
Dimitris Fotakis, Evangelia Gergatsouli, Themis Gouleakis, and Nikolas Patris. Learning augmented online facility location. CoRR, abs/2107.08277) 2021. URL. tattps://arxxr wwtp:iiww.rg/b/////////
08277
12

---

Buddhima Gamlath, Silvio Lattanzi, Ashkan Norouzi- Fardd and Ola Svensson. Approximate cluster recovery from noisy labels. In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 1463-1509. PMLR, 2022.
Suprovat Ghoshal, Konstantin Makarychev, and Yury Makarychev. Constraint satisfaction problems with advice. CoRR, htss/2403.022122 2024. doi: 10.4550/ARRXIV2400..222 URL https //doi.org/10 48550/ www.a..wwv...........
Michel X. Goemans and David Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6): 1 1145-145, 1995.
Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy buy with expert advice. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 2319-2327, PMLR, 2019.
Anupam Gupta, Debmalya Panigrahi, Bernardo Subercaseaux, and Kevin Sun. Augmenting online algorithms with e-accurate predictions. In NeurlPS, Dec 2022.
Jun-Ting Hsieh and Pravesh K. Kothari. Approximating max-cut on bounded degree graphs: Tighter analysis of the FKL algorithm. CoRR, 0ess/2206.992000 2022.
Shaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang. Online facility location with predictions. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022a.
Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. ACM Trans. Algorithms, 18(4):39:1-39:21 2022b.
Kasper Green Larsen, Michael Mitzenmacher, and Charalampos E. Tsourakakis. Clustering with a faulty oracle. In Yennun Huang, Irwin King, Tie Liu, and Maarten van Steen, editors, WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, pages IW3C2, 2020.
ACM/ /
Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schlöter. Minimalistic predictions to schedule jobs with online precedence constraints. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning. ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 18563-18583, PMLR, 2023.
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1859-1877. SIAM, 2020.
Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and instance-robust predictions for online matching, flows and load balancing. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference). volume 204 of LIPlcs, pages 59:1-59:17. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2021.
Alexander Lindermayr, Nicole Megow, and Martin Rapp. Speed-oblivious online scheduling: Know- ing (precise) speeds is not necessary. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Ma- chine Learning. ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 21312-21332 PMLR, 2023.
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J.
ACM, 68(4):24:1-24:255 2021.
Arya Mazumdar and Barna Saha. Clustering with noisy queries. Advances in Neural Information Processing Systems, 30, 2017.
13

---

Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of I.Plcss, pages 14:1-14:18. Schloss Dagstuhl -eebbniz-Zentrum für Informatik, 2020.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Press, 2020.
662. Cambridge University
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Commun, ACM, 65(7): 33-35, 2022.
Ryan O'Donnell, Analysis of boolean functions. Cambridge University Press, 2014.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via MI. predictions. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Bianchi, and Roman Garnett, editors, Advances Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 9684-9693, 2018.
Prasad Raghavendra and Ning Tan. Approximating CSPs with global cardinality constraints using sdp hierarchies. In Proceedings of the twenty-third annual ACM-SIAM symposium Discrete Algorithms, pages 373-387. SIAM, 2012.
Tim Roughgarden, editor. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press. 2020.
Alexander Wei. Better and simpler Borning-augmeett online caching. Jaroslaw Byrka and Raghu Meka, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of L.Plcs, pages 60:1-60:1 17. Schloss Dagstuhl Lentniz-Zentrum für Informatik, 2020.
Alexander Wei and Fred Zhang. Optimal robustness -onpssttsss-cssssteeeeyy trade-offs for learning augmented online algorithms. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Parria-Forrna Balcan, and Hsuan-Tices Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
14

---

Appendix
A Missing proofs for MAXCUT in the partial prediction model
Proof of Theorem 4.7 Given a graph G (V; F)) with the optimal (A*, B*) that cuts F E n E A" B"), let S be the set of vertices whose label is given, and let A = A US B = 8 US. Consider the following MAXCUT SDP that fixes the vertices with the revealed labels.
Ar, (1 vy))
max WE ViE(n)
Σ 5.jE/o]
s.t. U; = vn Vi E and U; = v0 E B.
2
Note that this is still a valid relaxation so the optimal SDP value sdp is at least opt. For each edge E", E(A, B) with probability z2; in other words, both of its endpoints will reveal their labels. Let r denotes the total weight of such edges, so that E[[] = =oop.. Note that sdp 2 opt for every partial prediction.
Perform the standard hyperplane rounding. For each E" n E(A, B), the rounding will always cut e. For all other edges, we have an approximation ratio of daw Therefore, the expected weight of the cut edges is at least
E[rW + (sGp WW) 2 ePopt + aIGW - - )opp (agw + (1 (Gw))=)) opt.
Proof of Theorem 4.2 Given a graph = EV with the optimal cut (A",B") that cuts E En E (AA,, }, let be the set of vertices whose label is given, and let A = A" US B B US.. Let E' be the set of the edges that are incident on A or B. Each edge cut in the optimal solution will be in E' with probability 2s 8². Let be the total weight of the edges in E" n F' so that B|r] (2s- E² jopt. Guess the value of r (up to a o(1) multiplicative error that we will ignore in the proof), and consider the following MAXCUT SDP that fixes the vertices with the revealed labels and requires a large SDP contribution from E".
A1 (us 02))
mnxx by W.S, ViE[n]
8.l. 01 0p
Vi A Vi B
0/ -uu
A1, - (vi, 0z))
(K))
Given the correctly guessed value of r, the optimal solution is still feasible for the above SDP, so sdp 2 opt. We use Raghavendra and Tan 2012 rounding algorithm, which is briefly recalled below.
For each i E [n]], define μ4 [-1,+11 and w; R" such that u; 14.00 + w; and wi 1 vo-
Let पेद = w:/ [ (w; = 0 if and only if 0; = -vp Then define कहद = 0.)
Pick random Gaussian vector orthogonal to tig- Let & == (g, wT) Note that each &, is standard Gaussian.
Let the threshold 4; = - 1/2) where & is the CDF of a standard Gaussian. & S 14, set J; = 1 and otherwise set J; =
Raghavendra and Tan showed that this rounding achieves an (agr R 0.858) apprrximaaoiiiiooonnn for every edge.
Consider an edge (i.j) E E' and without loss of generality, assume i E B, which implies that V Vu. The contribution of this edge the SDP objective is /2,2 + 1/2. Note that Pr[a, 1] is exactly 4 and B[r,] = (2,/2++ + 1/2) (1/2 - 22/ Py. So, we get a 1-approximation from this edge. Since other edges still have ORT approxiroiiittionn, the total expected weight of the edges cut is at least
(sd r]] 2 (2s -2p-==
-25- - =oo) = ogT opt + (1 - agr (2: -00==220pm )opt.
Hence the proof of Theorem 4.2
15

---

B Missing details for 2-CSPs
The goal of this section is to establish Theorem 5.2 for dense instances of 2-CSPs.
B.1 The 2-CSP Algorithm for Dense Instances
First observe that we may assume without loss of generality that each (wx, a) appears exactly twice in I. This is convenient so that for æ E {+1}", valz(z) Lie(m) (wwnnoess w P(ce With a slight abuse of notation, for all (ıc, G, a)) E S we let
Pico (xg Z))1))== =
Σ D xi (x) +
Σ c' a'l)xti
Dove Xo (x)
a Ca a'(1)=i
and
P(cozal)) = Σ D Xana)a)()) Σ
Pa (x)
a'Cast. d'()=i
a'Cast d'())
We further define $; C S; to be subset of constraints in S; that are not part of the A-prefix of i.
We state the algorithm behind Theorem 5.2 which amounts to the following two steps.
1. Solve the linear program
Σ
wP(co (x; (1..2%' zali))
11+1
TE (w,,,,)), A-wide
subject to
uP(corali) (w,,,a)eS
Σ
+ Σ
Σ
wP(coralt
<E|n
(Ein A wide
(w.ca)ESSA$.
A n-namow
Σ 1
Σ w (P(cozaat)) P(co z011) s SC(E' 1 W
(10)
(w,,,a)e&
for some large enough absolute constant C > 0. Let & [11,+11]] be the found optimal solution.
2. Repeat ((1/n) times independently and output the best assignment X independently for each E [n] set X, with probability (1 / and X, -1 otherwise.
The LP above generalize the one in jeq. (1) which comes as special case where A for all a' C Cac E [n]². Indeed, since predicates contain only two literals, the program is linear.
B.2 The Analysis of the 2-CSP Algorithm
We obtain here the proof of Theorem 5.2
Feasibility of the best assignment As in Lemma 3.5 first prove that, in expectation over the prediction Y, x=" is a feasible solution to the program.
Lemma B.1. Consider the settings of Theorem 5.2 Then
E Σ
Σ
xtalii))
Σ
Σ
uP(co xtali)
[m (w.cca))E.
ie A-wide
A narrow
Σ
Σ (w.c.a)Es
w (P(cox - P(co (accalt)-P(ppoaii -P)) I +
A-wide
16

---

Proof. First, by definition of A A-iide instance,
Σ
Σ
uP(cor S nWW
seini A-narrow
(w.caa)E,
Second, by definition for any A-wide vertex i,
Σ
uP(cor Sn...
Hence remains to show
E
Σ
Σ w (P(coztali)- P(co P(coz(11) & <((W((VA))
i wide
(1,Ga)eS
Now, recall that E|Y; 2 and thus E x²" So for any (c, E I, EiP(c o 2d) E[P(cox"") by pair-wist wise independence of the predictions. Thus suffices to study, for each A-wide
i, var Σ (w,,o))es wP(co z)li)) To this end, notice that for any a, E S; with a a = {i)
holds
P(co y P(co r = P(c rali) E Plco [P(cor
Moreover, since |ar| 2, there are most distinet negation patterns. Therefore, by the AM-GM inequality
Σ
wP(c o Zoli)) (011)
Σ
(w var (P(co 20(1))
var
(w,cc.)ES.
(w,ca;)E
w
Σ
E2
(w.c,))
where used the fact that entries of Z are bounded by 1/e and the coefficients of boolean predicate bounded by 1 (by Parseval's Theorem, see O'Donnell (2014)). By construction of S; each (w, c. St must satisfy S W,/A. Using Holder's inequality
Σ
wP(co Zair) (PP))
50
W? A
(w.C,a)ES,
We can use this bound on the variance in combination with Chebishev's inequality to obtain, for 0,
P Σ
(P(cor P(co zali)) 22) 0
W X2
(w,,,,)Es,
Let = O(W:/(evA) A peeling argument now completes the proof:
Σ w (P(coztarit - P(c zov))
(w.c,a)Es,
SAt Σ 21+1A.P
Σ w (P(cozzari)- P(co z0lli) (w.ca)ES
22'2 s0(2).
120
17

---

Analysis of the algorithm We can use Lemma B. to obtain our main theorem for CSPs.
Proof of Theorem 5.2 We follow closely the proof Lemma 3.6 Consider one of the assignments X E {+1} found in the second step of the algorithm. Recall ă [-1, +1]" denotes the optimal
fractional solution found by the algorithm. We may rewrite for each A-wide i and (w, c, a) E S,
Σ
Σ
wP(coXX)
Σ
Σ
P(co (ās (2al)))))
i (w.c,))E; A-wide
iE(n] (w,c,0EB
A-dide
+ P(co x*) p(co 8²))
+ Plco x²) P(co (#; z
(11)
We bound each term in Equation (1I) separately. First, notice that by Markov's inequality and Lemma B.I with probability 0.99, x² is feasible solution to the LP. Conditioning this event &
Σ
wP(co (&+ ))) 2
Σ (w.c,a)ES,
w PPcc (x) 22
iE|n (w,,,,)E,,
iE|n] A-wide
Σ
Σ
wP(cox*a)
iEju] A wide
(w,e,a)ES,
Σ
w (Plco (1z 2001)) P(e x x²a)
EE A-wide
(w,e,a)ES.
By Holder's inequality and the fact that x² is feasible, for A-wide
Σ kE(n) A-wide
Σ
w (P(co(a) )))1 P(cox"a)
(wr,,a)E,,
Σ w (P(c z P -(eco marrt) (0(E)) W.)
iEin A-wide
(w.c,))E
Since by construction & is feasible, another application of Holder's inequality also yields the following bound on the third term,
Σ
Σ w (P(co (as -aai))))) P(co < (0(5')+ W.
1 (w.C,O)ES.
A-wide
For the second term in Equation (11) by construction of X we have E [P(co xa) = P(cot9) Combining the three bounds, get that
opt, 2
E
1 W
Σ
Σ (w.,,,o)EE,
wP(co X²) E 2 optz (O(E') 4n)
(E(n] A-wide
Applying Markov's inequality on the random variable optz
# Σ
iE(ni E(w,oaess wP(co Xa). A-wide
we get
P
Σ
Σ
wP(co s opty (O(s') 5m) E 1+
A wide
The theorem follows since sample O(1/n) independent assignments X and pick the best.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Theorems 3.1 and 5.2 which are proved in the paper, formalize the claims in the abstract.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The models' assumptions are accurately described (see Section 2).
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are clearly stated. All theorems are formally proved in the main body in the appendix.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
9. Code Of Ethics
19

---

Question: Does the research conducted in the paper conform, in every respect. with the
NeurIPS Code of Ethics ftt.gittttee...ecrr...c/o//o//tr
Answer: [Yes]
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This is theoretical work; do not foresee any societal impact of this work.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
20


Reviews:
[{"review_id": "OZSloRB8mk", "reviewer": "Reviewer_PkHv", "summary": "The authors discuss about a setup if the approximation ratio of the known approximation algorithms for offline NP-hard problems can be improved in the cases where we have access to noisy or partial predictions. They answer this investigation positively for MaxCut and Constraint Satisfaction (CSP) problems. Their theoretical investigation proves that the worst-case performance for the MaxCut and 2-CSP problems can be improved with assuming access to pairwise independent predictions that are correct with the probability $1/2 + \\epsilon$. This corresponds to the noisy predictions setting. In the partial prediction settings, they assume that each vertex reveals their correct label with probability $\\epsilon$ pairwise independently. Similarly, this theoretically improves the worst-case performance for the MaxCut problem.", "questions": "My questions are in parallel with the weaknesses I listed above:\n- Could you please motivate more about the advantages of utilizing predictions in the offline setting with practical applications?\n- How does your setup differ from the works of [Bampis et al., 2024] and [Ghoshal et al., 2024]?\n- Do you think it is possible to define a computational upper bound on the cost of getting the predictions so that an approximation algorithm can still be considered polynomial? In other words, can there be a trade-off between the cost of predictions and the improvement on the worst-case bound?", "limitations": "Limitations of the paper are not explicitly discussed beyond the assumptions made in Section 2.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The central motivation of the paper is quite interesting. With the abundance of the prediction ML models, utilizing their outputs in improving the approximation guarantees of famous combinatorial optimization problems makes it a challenging discussion. The problem setups are explained clearly. Considering much of the related work focuses on the online setting, making contributions for the offline setting seems significant.", "weaknesses": "- The introduction could motivate the readers more about the significance of the offline setting. \n- On the first glance, it is not very clear how this papers differs from the concurrent work mentioned on the last paragraph of the Related Work (besides one of them making the full independence assumption between the predictions).\n- The existence of predictions is treated as a given but often times acquiring those predictions comes with a significant cost.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BZweZpphL3", "reviewer": "Reviewer_SRjy", "summary": "**Problem Studied**\n\nThis paper studies the Max Cut and 2-CSP problems in a setting where there is some noisy prediction of the optimal solution. In particular, the paper considers the following three settings:\n- Max Cut in the \"noisy prediction model\": Here, each vertex gives its true label with probability $\\frac{1}{2} + \\epsilon$ (and its opposite label otherwise). \n- Max Cut in the \"partial prediction model\": Here, an $\\epsilon$-fraction of the vertices reveal their true label at random.\n- 2-CSPs in the noisy prediction model.\n\n**Main Results / Contributions**\n\nFor Max Cut, the main result is that it is possible to beat the Goemans-Williamson approximation factor when $\\epsilon > 0$. For the noisy prediction model, the authors obtain an approximation ratio that is roughly $\\alpha_{GW} +  \\Omega(\\epsilon^4)$. For the partial prediction model, it is possible to get $\\alpha_{GW} + \\Omega(\\epsilon^2)$, or $\\alpha_{GT} + \\Omega(\\epsilon)$, where $\\alpha_{GT} \\approx 0.858$ is the approximation ratio of the algorithm by Raghavendra and Tan.\n\nThe authors extend one result to 2-CSPs in the noisy prediction model that are \"wide\".", "questions": "1. For the noisy prediction model of Max Cut, a natural algorithm that comes to mind is to return the better of the Goemans-Williamson cut and the predicted cut. Is there an example where this algorithm does not do better than $\\alpha_{GW}$?\n\n2. In the literature on algorithms with predictions, one common way people have modeled the \"prediction\" is as a single predicted solution, instead of assuming it is generated from a distribution. They then usually parameterize the performance of the algorithm (e.g. approximation ratio), as a function of the \"error\" in the (single) predicted solution, where \"error\" is something that has to be defined depending on the problem. This has the advantage of not needing to define the form of the distribution that the prediction comes from (like the noisy prediction model or the partial prediction model), and gives a somewhat more \"instance-dependent\" guarantee. What are your thoughts on this way of viewing the prediction in the context of your problem? Do you think it is a better or worse model, and why?\n\n3. As $\\epsilon \\to \\frac{1}{2}$ in the noisy predictions model, the prediction approaches the optimal solution, and so the approximation ratio of the algorithm should intuitively go to 1. Is this the case for the algorithm considered in this paper? This is not clear from the theorem statement because it has a big-Omega in the bound. Is there is a way to write the approximation ratio exactly in terms of $\\epsilon$ to show that it approaches 1 as $\\epsilon \\to \\frac{1}{2}$? If so, I think that would be instructive. Similarly for the partial predictions model as $\\epsilon \\to 1$. \n\n4. What is the intuition for why predictions are not needed for narrow instances?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is very well written. It is nice to read and the contributions of the paper are clear. It studies a natural variant (prediction-augmented) of a well-known problem (max cut). It also answers an open question posed by Ola Svensson, which is a good sign.", "weaknesses": "The title is perhaps promising more than the paper delivers -- the paper only studies Max Cut and a subclass of 2-CSP instances, so it is a bit misleading to use \"maximization problems\" in the title.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8yeCHRwOl6", "reviewer": "Reviewer_969c", "summary": "Authors study algorithms constraint satisfaction problems, in particular, MAX-CUT\nwhich are provided with predictions mildly correlated with the optimal solution.\nIn the case of MAX-CUT, we have a prediction +1 or -1 for each vertex of the graph\nwhich suggests which side of the maximum cut should it belong to.\nFor each vertex, this prediction is correct with probability 0.5+eps,\nassuming a pairwise independence between the predictions.\nThey call this eps-correlated predictions.\nThey also consider a similar model where all predictions are guaranteed to be correct\nbut they are available only for eps-fraction of the vertices chosen randomly.\n\nTheir main result is a poly-time algorithm for MAX-CUT which, given\neps-correlated predictions, achieves an improvement of order Omega(eps^4)\nover the best possible approximation ratio achievable by a poly-time algorithm\nwithout any predictions.\nTheir algorithm is based on combination of linear programming and semidefinite\nprogramming techniques.", "questions": "* Is the precision parameter of the predictions epsilon known to the algorithm?\n\n* Many works, especially for online problems, consider predictions whose error\nis distributed adversarially. Do you think such predictions are also applicable\nto MAX-CUT and CSPs?", "limitations": "properly stated in the theorem statements.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* I believe that the problem of solving MAX-CUT\nstarting with a solution which is mildly correlated with the optimum is a basic\nquestion about SDP techniques for MAX-CUT. Since MAX-CUT is one of the central\nproblems in theory of algorithms, I consider the progress on this question to\nbe the main strength of this paper.\n\n* the main clear model of MAX-CUT with eps-correlated predictions is also extended\nto CSPs and also to the model with partial predictions.", "weaknesses": "Nothing particular.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gFeBHjMwnC", "reviewer": "Reviewer_fPP4", "summary": "For the Max Cut Problem, the authors first consider predictions that are independently correct with probability 1/2 + $\\epsilon$ (noisy prediction model). They obtain an approximation guarantee of $0.878 + \\Omega(\\epsilon^4)$, improving upon best-known approximation guarantees. The idea of the algorithm is to divide instances by wide and narrow graphs, a notion related to high-degree and low-degree graphs. By obtaining approximation guarantees for both cases and optimizing over some parameters, they obtain their first main result.\nIn the second setting, they consider a partial prediction model, in which one gets a correct prediction, but only for an $\\epsilon$-fraction of randomly chosen vertices. In this case they obtain a $0.858 + \\Omega(\\epsilon)$ approximation algorithm, which is slightly worse than the $0.878$-approximation for small $\\epsilon$, but in general the dependency on $\\epsilon$ is more favorable. The slightly worse constant is because one needs to employ a rounding scheme from Raghavendra and Tan, which has this approximation guarantee. However, by doing this, one obtains a better dependency on $\\epsilon$.\nFinally, the authors also consider 2-CSPs in the noisy prediction model. The ideas are similar to the case for the Max Cut Problem.", "questions": "-", "limitations": "In my opinion, all limitations have been properly addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper is well-written and the proofs seem sound. The results are nice and improve upon state-of-the-art approximation algorithms given good predictions on the solution. To the best of my knowledge, this paper is the first to substantially contribute towards learning-augmented algorithms in the area of approximation algorithms. Hence, the paper is innovative and might lead to new results in this interesting area.", "weaknesses": "The results are specifically tailored for the problems considered in this paper. However, this is no surprise as this paper is the first to study learning-augmented algorithms in this area. Therefore, I do not see this as a strong weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission introduces a new model of advice for Max-Cut and similar CSPs. 
They design algorithms that can take advantage of such advice. 

The reviewers generally like the model and result, but there was a strong sentiment that the authors' title about generic "maximization problems" is a bit misleading. I agree and strongly encourage the authors to change their title to explicitly say Max-Cut / CSPs for their camera ready.
Decision: Accept (poster)