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_cc_2024_Conference
Published: 2024-05-15 10:37:51

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).

Main paper: 
 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 we use machine-learned information to solve 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 to design algorithms for inputs that are revealed sequentially over time. Indeed, assuming that the future unfolds in a typical rather than worst-case manner, we can compensate for the information deficit of the online algorithm with predictions learned based on past data, thereby helping it bypass information-theoretic lower bounds. This principle has been successfully applied to a broad range of online problems, such as caching [Lykouris and Vassilvitskii, 2021] , rent-or-buy [Purohit et al., 2018] , covering Bamas et al. [2020b] , network design Azar et al. [2022] , scheduling Azar et al. [2021] , matching Dinitz et al. [2021] , and many others (see related work for more references).In this paper, we study the role of machine-learned predictions in offline NP-hard problems. For offline problems, an algorithm has no information disadvantage compared to an optimal solution: the disadvantage is computational. The NP-hardness of problems makes exact algorithms that run in polynomial time unlikely. This has led to the field of approximation algorithms, where the goal is to obtain polynomial-time algorithms that output solutions that are approximately optimal. In 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 offline problem is also subject to computational barriers. For instance, for the classical MAXCUT problem, it is known that the approximation factor of α GW ≈ 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-learned predictions to overcome computational barriers to approximation algorithms for NP-hard problems?Suppose we are given a noisy prediction that is mildly correlated with an optimal solution for a given problem instance. Can we use such a prediction to recover a better approximation to the optimal solution than is possible without any prediction? For (strongly) NP-hard problems, we typically know barriers for the best approximation factor α 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-time algorithm with an approximation factor strictly better than α. The quantum of improvement naturally depends on the quality of the prediction: if the prediction is ε-correlated with the target solution, can we get an α + f (ε) approximation?To make these questions concrete, we first consider the MAXCUT problem in the learning-augmented 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 widely-accepted unique games conjecture, the Goemans-Williamson approximation bound of α GW ≈ 0.878 is the best possible for a polynomial-time algorithm. But, suppose we are given a prediction for the optimal max-cut that is independently correct for every vertex with probability 1 /2 + ε, for any ε > 0. (Note that random guessing achieves correctness of 1 /2; so, we assume that the prediction is only ε-better than random guesses.) Can this prediction be used to obtain an approximation factor better than α GW in polynomial time? This question was posed by Svensson in his SODA 2023 plenary lecture.Our first result is to unconditionally improve on worst-case performance for the MAXCUT problem using an ε-correlated prediction. This answers the question posed by Svensson in the affirmative. Specifically, we give an algorithm that obtains an (α GW + Ω(ε 4 ))-approximate 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 on the vertices. This is significant because in practice, the predictions for the different vertices are likely to be obtained from a machine learning model or a human expert, either of which sources are unlikely to output 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 a correct prediction but only for an ε-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 (α RT + Ω(ε))-approximate solution to MAXCUT, where α RT ≃ 0.858 is the approximation factor obtained by Raghavendra and Tan for the MAXBISECTION problem [Raghavendra and Tan, 2012] . Note that α RT is slightly smaller than α GW , but we get a better advantage of Ω(ε) instead of Ω(ε 4 ).Next, we show that our algorithmic framework is applicable beyond the MAXCUT problem. Constraint Satisfaction Problems (CSPs) are a broad class of optimization problems that includes fundamental optimization tasks such as MAX-k-SAT, 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. A classical result of Arora et al. [1999] 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 ε-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 a function of the prediction bias and the approximation error) for our result in the learning-augmented setting is weaker than that of Arora et al. [1999] , i.e., our result applies to a broader set of instances.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. In clustering, Ashtiani et al. [2016] introduced a setting where an algorithm can query an external oracle (e.g., a machine learning model) to learn if a pair of points are in the same cluster in the optimal clustering (same-cluster queries). The goal then is to recover an optimal solution (or a 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., 2018] 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] . Another line of work Ergun et 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 + o(1))-approximation to the k-means objective as long as the clusters are not too small.A different line of work has aimed to incorporate machine-learned predictions in the design of online algorithms (see, e.g., the surveys Mitzenmacher and Vassilvitskii [2020, 2022] ). This model was introduced by Lykouris and Vassilvitskii for the caching problem Lykouris and Vassilvitskii [2021] and has since been studied in many problem domains such as rent or 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 al. [2021], Cohen and Panigrahi [2023] , Lindermayr et al. [2023] , Lassota et al. [2023] , caching Lykouris and Vassilvitskii [2021] , Wei [2020] , Jiang et al. [2022b] , Bansal et al. [2022] , matching Dinitz et al. [2021] , Lavastida et al. [2021] , secretary problems Antoniadis et al. [2020b] , Dütting et al. [2021] , graph problems Antoniadis et al. [2020a] , Jiang et al. [2022a] , Almanza et al. [2021] , Antoniadis et al. [2023] , Bernardini et al. [2022] , Anand et al. [2022] , Fotakis et al. [2021] , Azar et al. [2022] , and many others. (The reader is referred to ALP [2023] for a compendium of papers in this area.) The main goal in this line of work is to overcome information-theoretic 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 Bampis 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 -ε) 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 Ω(n 2 / log n), 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 a (1 -O((ε√ ∆) -1))-approximation for both models, where ∆ 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 -n ij w 2 ij ε -1 . 
preliminaries: 
 The MAXCUT Problem. We start by describing the MAXCUT problem. In this problem, we are given a weighted graph G = (V, E) represented by a (symmetric) n × n adjacency matrix A, where A ij = w ij , 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 i = j w ij denote the weighted degree of vertex i. We use D := diag(W 1 , . . . , W n ) 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 ∈ {-1, 1} n denotes a cut in the graph, and the quadratic form ⟨x, Lx⟩ = {i,j}∈E w ij (x i -x j ) 2 counts (four times) the weight of edges crossing the cut between the vertices labeled 1, and those labeled -1.The MAXCUT problem asks for the cut with maximum edge weight. Hence, MAXCUT can be rephrased as follows:MAXCUT(G) := max x∈{-1,1} n 1 /4 • ⟨x, Lx⟩.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 5.1. In the noisy predictions model for MAXCUT, we assume there is some fixed and unknown optimal solution x * ∈ {-1, 1} n . The algorithm has access to a prediction vector Y ∈ {-1, 1} n , such that for each vertex i, Y i is the correct label x * i with some (unknown) probability 1 /2 + ε, and is the other (incorrect) label with probability 1 /2 -ε. Here we only assume pairwise independence; for any two vertices i and j, Pr[i, j both give their correct labels] = ( 1 /2 + ε) 2 .2. In the partial predictions model for MAXCUT, the algorithm has access to a prediction vector Y ∈ {-1, 0, 1} n such that for each vertex i, Y i is the correct label x * i with some (unknown) probability ε 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] = ε 2 . 
maxcut in the noisy prediction model: 
 Recall that in the noisy prediction model, the predicted label of each vertex is its correct label in a fixed max-cut with probability 1 /2 + ε. Moreover, the labels are pairwise independent. One can show that in this model, if one were to simply output the prediction itself, then its value would be at least O(m/2 + ε 2 (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 MAXCUT algorithm. Our main result is to give an algorithm that uses a noisy prediction to outperform α GW in the approximation bound by an additive poly(ε) factor: Theorem 3.1 (Noisy Predictions). Given noisy predictions with a bias of ε, there is a polynomial-time randomized algorithm that obtains an approximation factor of α GW + Ω(ε 4 ) in expectation for the MAXCUT problem.The rest of this section is devoted to proving the above theorem. A basic distinction that we will use throughout this section is that of ∆-wide and ∆-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 ∆-wide graphs in §3.1, followed by the result for ∆-narrow graphs in §3.2. We finally wrap up with the proof of Theorem 3.1.We partition the edges incident to vertex i into two sets: the ∆-prefix for i comprises the ∆ heaviest edges incident to i (breaking ties arbitrarily), while the remaining edges make up the ∆-suffix for i. We fix a parameter η ∈ (0, 1 /2). We will eventually set ∆ = Θ(1/ε 2 ) and η to be an absolute constant. Recall that W i = j∈[n] A ij is the weighted degree of i. Definition 3.2 (∆-Narrow/Wide Vertex). A vertex i is ∆-wide if the total weight of edges in its ∆-prefix is at most ηW i , and so the weight of edges in its ∆-suffix is at least(1 -η)W i . Otherwise, the vertex i is ∆-narrow.Intuitively, 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 ∆-wide and ∆-narrow sets; these are respectively denoted V >∆ and V <∆ . We define W >∆ := i∈V>∆ W i and W <∆ := i∈V<∆ W i , and hence the sum of weighted degrees of all vertices is W := n i=1 W i = W >∆ + W <∆ . Definition 3.3 (∆-Narrow/Wide Graph).A graph is ∆-wide if the sum of weighted degrees of ∆-wide vertices accounts for at least 1-η fraction of that of all vertices; i.e., ifW >∆ ≥ (1-η)W . Otherwise, it is ∆-narrow.For ∆-wide graphs, we show: Theorem 3.4. Fix ε ′ ∈ (0, 1). Given noisy predictions with bias ε, there is a polynomial-time randomized algorithm that, given any ∆-wide graph, outputs a cut of value at least the maximum cut minus (5η + 2ε ′ )W , where ∆ := O(1/(ε • ε ′ ) 2 ), with probability 0.98.Since the graph is ∆-wide, most vertices have their weight spread over a large number of their neighbors. In this case, the prediction vector allows us to obtain a good estimate r 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 to assign fractional labels to vertices that maximize the cut value while remaining faithful to these estimates r; finally rounding the LP gives the solution.Define an n × n matrix Ã from the adjacency matrix A as follows: for each row corresponding to the edges incident to a vertex i, we set the entry Ãij = 0 if the edge (i, j) is in the ∆-prefix of vertex i; otherwise, Ãij = A ij . Now, define an n-dimensional vector r as follows:ri = 1 2ε ( ÃY ) i if i is ∆-wide 0 if i is ∆-narrowwhere Y is the prediction vector. Solve the linear program:min x∈[-1,1] n ⟨r, x⟩ s.t. ∥r -Ax∥ 1 ≤ (ε ′ + 2η)W.(1)Let x ∈ [-1, 1] n be the optimal LP solution.Finally, do the following O( 1 /η) times independently, and output the best cut X * among them: randomly round the fractional solution x independently for each vertex to get a cutX ∈ {-1, 1} n ; namely, Pr[X i = 1] = (1+xi) /2 and Pr[X i = -1] = (1-xi) /2.For a labeling x ∈ {-1, 1} n , the neighborhood imbalance for vertex i is defined as j A ij x j = (Ax) i . 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 x. The maximality of the optimal cut x * ∈ {-1, 1} n ensures that x * i • sign((Ax * ) i ) ≤ 0 for all i; else, switching x i from 1 to -1 or vice-versa increases the objective. Define r * := Ax * as the vector of imbalances for the optimal cut. Lemma 3.5. The vector r satisfiesE [∥r -r * ∥ 1 ] := E n i=1 |r i -r * i | ≤ O W ε √ ∆ + 2ηW.Proof. Observe thatE[Y i ] = x * i • Pr[Y i = x * i ] -x * i • Pr[Y i = -x * i ] = x * i ( 1 /2 + ε) -x * i ( 1 /2 -ε) = 2εx * i . Define Z := 1 2ε Y . Then, E[Z] =x * , and so E[AZ] = r * . First, we consider a ∆-narrow vertex i. Since ri = 0, we haveEQUATIONsince the graph is ∆-wide.Now, we consider a ∆-wide vertex i. We haveEQUATIONTo bound the first term in the RHS of (3), recall that r *i = E[(AZ) i ]. Thus, |E[( ÃZ) i ] -r * i | = |E[( ÃZ) i ] -E[(AZ) i ]| = ⟨( Ã -A) i , E[Z]⟩. Since E[Z] = x * ∈ {-1, 1} n , we get |E[( ÃZ) i ] -r * i | = ( Ã -A) i • x * ≤ ∥( Ã -A) i ∥ 1 ∥x * ∥ ∞ ≤ ηW i, where in the last step, we used the fact that i is a ∆-wide vertex. Now, we bound the second term in the RHS of (3). Using Chebyshev's inequality on the sum ( ÃZ) i = j Ãij Z j , we getPr[|( ÃZ) i -E[( ÃZ) i ]| ≥ λ i ] ≤ var(( ÃZ) i ) λ 2 i .Since the variables Z j are pairwise independent, the variance var((ÃZ) i ) = j Ã2 ij var(Z j ). The variance of each Z j is O(1/ε 2 ). For j Ã2 ij , we know j∈[n] Ã2 ij = ∥ Ãi ∥ 2 2 ≤ ∥ Ãi ∥ 1 • ∥ Ãi ∥ ∞ .Note that the weight of any edge in the ∆-suffix of i is at most W i /∆. Therefore, by our definition ofÃ, we have ∥ Ãi ∥ ∞ ≤ W i /∆. Since Ãij ≤ A ij for all j ∈ [n], we also have ∥ Ãi ∥ 1 ≤ ∥A i ∥ 1 = W i .Applying these bounds, we get:j∈[n] Ã2 ij ≤ W 2 i /∆. Therefore, E[|( ÃZ) i -E[( ÃZ) i ]|] ≤ var(( ÃZ) i ) ≤ O(W i /(ε √ ∆)).Summing over all ∆-wide vertices, we getE i∈V>∆ |r i -r * i | ≤ O W >∆ ε √ ∆ + ηW >∆ ≤ O W ε √ ∆ + ηW.Combining with (2) for ∆-narrow vertices, we getE [∥r i -r * i ∥ 1 ] ≤ O W ε √ ∆ + 2ηW.Now using Markov's inequality with Lemma 3.5, we get that setting ∆ = Ω(1/(εε ′ ) 2 ) for any fixed constant ε ′ > 0 ensures that we get a vector of empirical imbalances r satisfyingEQUATIONwith probability at least 0.99. (Since the 2ηW losses are deterministically bounded, we can use Markov's inequality only on the random variable i∈V>∆ |( ÃZ) i -E[( ÃZ) i ]|.) Hence, when the event in (4) happens, the vector x * is a feasible solution to LP (1).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 L and some x ∈ {-1, 1} n , the cut value isEQUATION)Lemma 3.6. For any ∆-wide graph, the algorithm from §3.1.1 outputsX * ∈ {-1, 1} n that satisfies f (X * ) ≥ f (x * ) -(2ε ′ + 5η)Wwith probability at least 0.98.Proof. Recall that the cut X * is the best among T := O( 1 /η) independent roundings of cut x. Consider one of the roundings X, and write:⟨X, AX⟩ = ⟨x, r⟩ + (⟨x, Ax⟩ -⟨x, r⟩) + (⟨X, AX⟩ -⟨x, Ax⟩).Let us first bound the expectation of each of the terms in the RHS of ( 6) separately.To bound the first term ⟨x, r⟩, note that given (4) (which happens with probability 0.99), the solution x * is feasible for the LP in (1). This means the optimal solution x has objective function valueEQUATIONNext, we bound the second term (⟨x, Ax⟩ -⟨x, r⟩) byEQUATIONby feasibility of x for the LP in (1). Finally, we bound the third term (⟨X, AX⟩ -⟨x, Ax⟩), this time in expectation:EQUATIONChaining eqs. ( 7) to ( 9) for the various parts of (6), we getE[⟨X, AX⟩] ≤ ⟨x * , Ax * ⟩ + (2ε ′ + 4η)W.Moreover, using that ⟨X, AX⟩ ∈ [-W, W ], we getPr ⟨X, AX⟩ ≥ E[⟨X, AX⟩] + ηW = Pr ⟨X, AX⟩ + W ≥ E[⟨X, AX⟩] + (1 + η)W ≤ Pr ⟨X, AX⟩ + W ≥ (1 + η/2) E[⟨X, AX⟩] + W ≤ 1 /(1+η/2).If X * is the cut with the smallest value of ⟨X, AX⟩ among all the independent roundings:Pr ⟨X * , AX * ⟩ ≤ ⟨x * , Ax * ⟩ + (2ε ′ + 5η)W ≥ 1 -( 1 /(1+η/2)) T ≥ 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 a simple pipeage rounding algorithm to round the fractional solution x to an integer solution X * without suffering any additional loss. Indeed, viewing ⟨x, Ax⟩ as a function of some x i keeping the remaining {x 1 , . . . , x n } \ {x i } fixed gives us a linear function of x i (since the diagonals of A are zero). Hence we can increase or decrease the value of x i to decrease ⟨x, Ax⟩ until x i ∈ {-1, 1}. Iterating over the variables gives the result. However, this does not change the result qualitatively.Next, we consider ∆-narrow graphs. We show: Theorem 3.7. For any ∆ ∈ N, there is a randomized algorithm for the MAXCUT problem with an (expected) approximation factor of α GW + Ω(η 5 /∆ 2 ) on any ∆-narrow graph.For the case of ∆-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 ∆ is clearly ∆-narrow (even when η = 1).We show that Theorem 3.7 holds for the Feige, Karpinski, and Langberg (FKL) MAXCUT algorithm [Feige et al., 2002] . We briefly recall this algorithm first. Consider the MAXCUT SDP with triangle inequalities:max vi∈Sn ∀i∈[n] i<j∈[n] A i,j • 1 -⟨v i , v j ⟩ 2 s.t. ∥av i -bv j ∥ 2 2 + ∥bv j -cv k ∥ 2 2 ≥ ∥av i -cv k ∥ 2 2 ∀i, j, k ∈ [n], a, b, c ∈ {-1, 1}.where S n is the unit sphere of n dimensions. Let v be an optimal solution to this SDP.Let g be a 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 v to x ∈ {-1, 1} n as follows: if ⟨v i , g⟩ > 0, then xi = 1; else, xi = -1.Now, define F = {i ∈ [n] : ⟨v i , g⟩ ∈ [-δ, δ]} for some δ = Θ(1/((∆/η) log(∆/η))). We partition N i := [n]\{i} as follows: B i := {j ∈ N i \F : xj = xi }, and C i := {j ∈ N i \F : xj ̸ = xi } and D i := N i ∩ F . We define F ′ ⊆ F as follows: i ∈ F ′ if i ∈ F and w(B i ) > w(C i ) + w(D i )where w(S) := j∈S A ij . In the final output X ∈ {-1, 1} n , we flip the vertices in F ′ , namelyX i = -x i if i ∈ F ′ , else X i = xi .We now give an analysis for the FKL algorithm establishing Theorem 3.7.The "local gain" for a vertex i ∈ F is defined as∆ i := (|B i | -(|D i | + |C i |)) +, where z + = max(z, 0). We now state the following key lemmas: Lemma 3.8. For any vertex i ∈[n], Pr[i ∈ F ] = Ω(δ).Proof. This lemma immediately follows from [Hsieh and Kothari, 2022, Fact 3] .Let i be a ∆-narrow vertex, and w ∈ R n be its weight vector (w i = A ij for all j ∈ [n]) so that W i = ∥w i ∥ 1 . Let w ′ ∈ R n be the projection of w onto its top ∆ coordinates. The narrowness of i implies that ∥w ′ ∥ 1 ≥ η∥w∥ 1 , which implies that∥w∥ 2 2 ≥ ∥w ′ ∥ 2 2 ≥ ∥w ′ ∥ 2 1 ∆ ≥ η 2 ∥w∥ 2 1 ∆ .It turns out that the analysis of Hsieh and Kothari [2022] still holds under the above bound between ℓ 1 and ℓ 2 norms of weight vectors. So we have the following slight generalization of their Lemma 8. Lemma 3.9 (extends Lemma 8 of Hsieh and Kothari [2022] ). There is a large enough constant C such that for any d ≥ 3 and δ = 1 Cd √ log d , for any vertex i whose weight vector w satisfies ∥w∥ 2 1 ≤ d∥w∥ 2 2 , it holds that the expected local gain of a vertex i satisfies:E[∆ i |i ∈ F ] = Ω W i d √ log d .Proof. In Hsieh and Kothari [2022] , the only place where the degree bound d is used is ∥w∥ 2 1 ≤ d∥w∥ 2 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 x by i∈F ′ ∆ i , i.e.,E[⟨X, LX⟩] = E[⟨x, Lx⟩] + i∈[n] E[∆ i |i ∈ F ] • Pr[i ∈ F ] ≥ E[⟨x, Lx⟩] + i:∆-narrow E[∆ i |i ∈ F ] • Pr[i ∈ F ].Let the approximation factor of the cut x output by the Goemans-Williamson algorithm be denoted α GW and let opt be the size of the maximum cut. Then,E[⟨x, Lx⟩] ≥ α GW • opt.From Lemmas 3.8 and 3.9 with d = ∆/η 2 , we getE[⟨X, LX⟩] ≥ α GW • opt + Ω 1 (∆/η 2 ) log(∆/η 2 ) • i:∆-narrow W i (∆/η 2 ) log(∆/η 2 ) . Since i:∆-narrow W i ≥ ηW ≥ 2η • opt, we get E[⟨X, LX⟩] ≥ (α GW + Ω(η 5 /∆ 2 )) • opt.For ∆-wide graphs, Theorem 3.4 returns a cut with value at least opt -(2η + ε ′ )W with probability 0.98. Since we can always find a cut of value α GW • opt, and opt ≥ W/2, this means the expected cut value is at least 0.98 • (1 -6η -2ε ′ ) + 0.02 • α GW opt. And for ∆-narrow graphs, Theorem 3.7 finds a cut with expected value α GW + Ω(η 5 /∆ 2 ) • opt. Moreover, recall that ∆ = O(1/(εε ′ ) 2 ).Setting η, ε ′ to be suitably small universal constants gives us that both the above approximation factors are at least α GW + Ω(ε 4 ), which proves Theorem 3.1. 
maxcut in the partial prediction model: 
 We now consider the partial prediction model, where each vertex pairwise-independently reveals their correct label with probability ε. Intuitively, this prediction model provides more information than the noisy prediction model since all predictions are guaranteed to be correct. Indeed, this is reflected in out first bound: we show that since an ε 2 fraction of the edges are induced by the vertices with the given labels, it is easy to get an approximation ratio of almost α GW + Ω(ε 2 ). (We give details in Appendix A.) Theorem 4.1. Given noisy predictions with a rate of ε, there is a polynomial-time randomized algorithm that obtains an (expected) approximation factor of α GW + ε 2 for the MAXCUT problemAlthough the Ω(ε 2 ) advantage in this theorem is already better than Ω(ε 4 ) in Theorem 3.1, we ask if can we do even better given the more informative predictions. Ideally, we could get an Ω(ε)-advantage if the hyperplane rounding performs better than α GW for the edges with only one endpoint's label revealed. One naive way to achieve this is to hope that the rounding preserves the marginals; i.e.,E[x i ] = ⟨v 0 , v i ⟩ for all i ∈ [n].In that case, if we consider (i, j) where if v i = ±v 0 , the probability that (i, j) is cut is exactly their contribution to the SDP (1 -⟨v i , v j ⟩).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 α RT ≈ 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 ε, there is a polynomialtime randomized algorithm that obtains an (expected) approximation factor of α RT + (1 -α RTo( 1))(2ε -ε 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, we extend Theorem 3.4 to this broader class of problems. Let us first define Max-2-CSPs (Constraint Satisfaction Problems). Each constraint is a 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., if the predicate is Not-Equals, and constraints form the edges of some graph, we get the MAXCUT problem.)Formally, for a multi-index α ∈ [n] 2 we denote by α(i) its i-th index and by x α the pair (x α(1) , x α(2) ).For variables x 1 , . . . , x n , we then write χ α (x) for the monomial i∈α x i . Given a predicate P : {-1, +1} 2 → {0, 1} , an instance I of the CSP(P) problem over variables x 1 , . . . , x n is a multi-set of triplets (w, c, α) representing constraints of the form P (c 1 x α(1) , c 2 x α(2) ) = 1 where α ∈ [n] 2 is the scope, c ∈ {±1} 2 is the negation pattern and w ≥ 0 is the weight of the constraint. For brevity we often write P (c • x α ) in place of P (c 1 x α(1) , c 2 x α(2) ). We let W = (w,c,α)∈I w . We can represent the predicate P as the multilinear polynomial of degree 2 in indeterminates x α(1) , x α(2) ,P (c • x α ) = α ′ ⊆α c α ′ • p(α ′ ) • χ α ′ (x) ,where p(α ′ ) is the coefficient in P of the monomial χ α ′ (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 a predicate P , an instance I of CSP(P) with m constraints and x ∈ {±1} n , we defineval I (x) := 1 W (w,c,α)∈I w • P (c • x α ) and opt I := max x∈{±1} n val I (x) .For instance, MAXCUT on a graph G = ([n], E) can be captured in this framework where P (x, y) = (1 -xy)/2, each edge (i, j) ∈ [n] 2 yields a triplet (w, c, α) where w = 1, c = (1, 1) and α = (i, j).In the noisy prediction model for CSPs, for an instance I of CSP(P), we assume there is some fixed assigment x * with value val I (x * ) = opt I . The algorithm has access to a prediction vector Y ∈ {±1} n such that predictions y i 's are 2-wise independently correct with probability 1+ε 2 for unknown bias ε . We let Z = Y 2ε . With a slight abuse of notation we also write P (c • Z α ) even though Z is a rescaled boolean vector.For a literal i ∈ [n] and an instance I of CSP(P) we let S i := {(w, c, α) ∈ I | α(1) = i} . As in Section 3.1.1, we can define ∆-wide literals and instances. For an instance I , we partition the constraints in S i into two sets: the ∆-prefix for i comprises the ∆ heaviest constraints in S i (breaking ties arbitrarily), while the remaining constraints make up the ∆-suffix for i, which we denote by Si . We fix a parameter η ∈ (0, 1 /2). We let W i = (w,c,α)∈Si w i .Definition 5.1 (∆-Narrow/Wide). A literal i is ∆-wide if the total weight of its in its ∆-prefix is at most ηW i , and so the weight of edges in its ∆-suffix is at least (1 -η)W i . Otherwise, the literal i is ∆-narrow. An instanceI of CSP(P) is ∆-wide if i∈[n] ∆-wide W i ≥ (1 -η)W .We are now ready to state the main theorem of the section. Theorem 5.2. Let P : {±1} 2 → {0, 1} be a predicate. Let ε ′ ∈ (0, 1) , η ∈ (0, 1/2) and ∆ ≥ O(1/(ε ′ • ε) 2 ). There exists a polynomial-time randomized algorithm that, given a ∆-wide I in CSP(P) and noisy predictions with bias ε, returns a vector x ∈ {±1} n satisfyingval I (x) ≥ opt I -5η -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. 
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 + ε; we can easily extend to the case where each node has a prediction that is correct with some probability 1 /2 + ε i , and each ε i ∈ Θ(ε). Can we extend to the case when we are only guaranteed ε i ≥ ε for every i? 2. For which other problems can we improve the performance of the state-of-the-art algorithms using noisy predictions? As we showed, the ideas used for the ∆-wide case extend to more general maximization 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? 3. What general lower bounds can we give for our prediction models? We feel that α GW +O(ε) is a natural barrier. One "evidence" we have is the following integrality gap for the SDP used in the partial information model; starting from a gap instance and an SDP solution exhibiting opt ≤ α GW • sdp for the standard SDP (without incorporating revealed information), given labels for an εn vertices, our new SDP simply fixes the positions of the corresponding εn vectors, but doing that from the given SDP solution decreases the SDP value by at most O(ε) in expectation, which still yields opt ≤ (α GW + O(ε))sdp. (Note that you can 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)?The goal of this section is to establish Theorem 5.2 for dense instances of 2-CSPs.First observe that we may assume without loss of generality that each (w, c, α) appears exactly twice in I . This is convenient so that for all x ∈ {±1} n , valI (x) = i∈[n] (w,c,α)∈Si w • P (c • x α ) .With a slight abuse of notation, for all (w, c, α) ∈ S i , we letEQUATIONP (c • x α\i ) := α ′ ⊆α s.t. α ′ (1)=i pα ′ c α ′ χ α ′ \α ′ (1) (x) + α ′ ⊆α s.t. α ′ (1)̸ =i pα ′ c α ′ χ α ′ (x) ,We further define Si ⊆ S i to be subset of constraints in S i that are not part of the ∆-prefix of i .We can now state the algorithm behind Theorem 5.2, which amounts to the following two steps.1. Solve the linear programEQUATIONfor some large enough absolute constant C > 0 . Let x ∈ [-1, +1] n be the found optimal solution. 2. Repeat O(1/η) times independently and output the best assignment X * : independently for each i ∈ [n] set X i = 1 with probability (1 + xi )/2 and X i = -1 otherwise.The LP above generalize the one in eq. ( 1), which comes as a special case where pα ′ = 0 for all α ′ ⊂ α ∈ [n] 2 . Indeed, since predicates contain only two literals, the program is linear.We obtain here the proof of Theorem 5.2.Feasibility of the best assignment As in Lemma 3.5, we 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. ThenE i∈[n] ∆-narrow (w,c,α)∈Si wP (c • x * α\i ) + i∈[n] ∆-wide (w,c,α)∈Si\ Si wP (c • x * α\i ) + i∈[n] ∆-wide (w,c,α)∈ Si w P (c • x * α\i ) -P (c • Z α\i ) ≤ W (2η + O(1/ε √ ∆)) .Proof. First, by definition of ∆-wide instance,i∈[n] ∆-narrow (w,c,α)∈Si wP (c • x * α\i ) ≤ ηW .Second, by definition for any ∆-wide vertex i,(w,c,α)∈Si\ Si wP (c • x * α\i ) ≤ ηW i .Hence it remains to showE i∈[n] ∆-wide (w,c,α)∈ Si w P (c • x * α\i ) -P (c • Z α\i ) ≤ O(W/(ε √ ∆) . Now, recall that E[Y i ] = 2εx * i and thus E[Z] = x * . So for any (c, α) ∈ I , E[P (c • Z α )] = E[P (c • x * α )] by pair-wise independence of the predictions. Thus it suffices to study, for each ∆-wide i, var (w,c,α)∈Si wP (c • Z α\i ) . To this end, notice that for any α, α ′ ∈ S i with α ∩ α ′ = {i} it holds Analysis of the algorithm We can use Lemma B.1 to obtain our main theorem for CSPs.E P (c • Y α\i )P (c • Y α ′ \i ) = E P (c • Y α\i ) E P (c • Y α ′ \i ) .Proof of Theorem 5.2. We follow closely the proof of Lemma 3.6. Consider one of the assignments X ∈ {±1} n found in the second step of the algorithm. Recall x ∈ [-1, +1] n denotes the optimal fractional solution found by the algorithm. We may rewrite for each ∆-wide i and (w, c, α) ∈ Si The theorem follows since we sample O(1/η) independent assignments X and pick the best. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - The introduction could motivate the readers more about the significance of the offline setting. 
- 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).
- The existence of predictions is treated as a given but often times acquiring those predictions comes with a significant cost.
questions: questions: My questions are in parallel with the weaknesses I listed above:
- Could you please motivate more about the advantages of utilizing predictions in the offline setting with practical applications?
- How does your setup differ from the works of [Bampis et al., 2024] and [Ghoshal et al., 2024]?
- 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: Limitations of the paper are not explicitly discussed beyond the assumptions made in Section 2.
paper_summary: paper_summary: **Problem Studied**

This 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:
- 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). 
- Max Cut in the "partial prediction model": Here, an $\epsilon$-fraction of the vertices reveal their true label at random.
- 2-CSPs in the noisy prediction model.

**Main Results / Contributions**

For 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.

The authors extend one result to 2-CSPs in the noisy prediction model that are "wide".
strength_weakness: strength_weakness: 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.
questions: 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}$?

2. 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?

3. 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$. 

4. What is the intuition for why predictions are not needed for narrow instances?
limitations: limitations: Yes.
paper_summary: paper_summary: Authors study algorithms constraint satisfaction problems, in particular, MAX-CUT
which are provided with predictions mildly correlated with the optimal solution.
In the case of MAX-CUT, we have a prediction +1 or -1 for each vertex of the graph
which suggests which side of the maximum cut should it belong to.
For each vertex, this prediction is correct with probability 0.5+eps,
assuming a pairwise independence between the predictions.
They call this eps-correlated predictions.
They also consider a similar model where all predictions are guaranteed to be correct
but they are available only for eps-fraction of the vertices chosen randomly.

Their main result is a poly-time algorithm for MAX-CUT which, given
eps-correlated predictions, achieves an improvement of order Omega(eps^4)
over the best possible approximation ratio achievable by a poly-time algorithm
without any predictions.
Their algorithm is based on combination of linear programming and semidefinite
programming techniques.
strength_weakness: strength_weakness: Nothing particular.
questions: questions: * Is the precision parameter of the predictions epsilon known to the algorithm?

* Many works, especially for online problems, consider predictions whose error
is distributed adversarially. Do you think such predictions are also applicable
to MAX-CUT and CSPs?
limitations: limitations: properly stated in the theorem statements.
paper_summary: paper_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.
In 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$.
Finally, the authors also consider 2-CSPs in the noisy prediction model. The ideas are similar to the case for the Max Cut Problem.
strength_weakness: strength_weakness: 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.
questions: questions: -
limitations: limitations: In my opinion, all limitations have been properly addressed.

Comments: comment: Thank you for your detailed response, I appreciate it!
thank you for your answers.
We thank the reviewer for the comments and the constructive encouragement.
We thank the reviewer for the comments and the constructive feedback.

- *Is the precision parameter of the predictions epsilon known to the algorithm?*

The parameter $\varepsilon$ does not need to be known: for example, we can run our algorithm for each $\varepsilon$ that’s a power of $\frac{1}{2}$ (between $\frac{1}{n}$ and $1$), and return the best of these solutions. One of these will be the right choice of $\varepsilon$, and our analysis holds for that choice of $\varepsilon$. (We will clarify this in the next version of the paper.)

- *Many works, especially for online problems, consider predictions whose error is distributed adversarially. Do you think such predictions are also applicable to MAX-CUT and CSPs?*

In general, giving the adversary power to choose the vertices it gives correct information on can make the predictions useless. For example, consider an instance containing $(1-\delta)n$ isolated vertices, and an arbitrary “hard” graph on the remaining $\delta n$ vertices. Now the adversary may only provide correct predictions on those isolated vertices.

So, we need to make some assumptions to avoid these pathologies. For example, if we assume that the graph is regular, our Theorem 4.1 for partial predictions that gives $0.858 + \Omega(\epsilon)$ approximation goes through even with deterministic predictions. A similar result holds in general graphs for deterministic predictions satisfying other properties. E.g., if an $\epsilon$ fraction of neighbors’ labels are revealed for every vertex, or more generally, if an $\epsilon$ fraction of edges are incident to the vertices whose labels are revealed. We will include a discussion about deterministic predictions in the Closing Remarks. We hope that our work will spur future investigation into such prediction models.
Thanks for the comments and constructive encouragement.

- *For the noisy prediction model of Max Cut, a natural algorithm that comes to mind is to return the better of the GW cut and the predicted cut. Is there an example where this algorithm does not do better than $\alpha_{GW}$?*

Yes: consider the tight instances for GW rounding (ones that achieve $\alpha_{GW}$ times the max-cut): such instances were given by Alon, Sudakov, and Zwick, and have maximum cuts that cut about 84.5% of the edges. Given any graph, the predicted labeling cuts each edge in the max-cut with probability $\frac{1}{2} + 2 \varepsilon^2$ and every other edge with probability $\frac{1}{2} - 2 \varepsilon^2$, thereby cutting a bit more than half the edges of the graph for small $\varepsilon$. So on the tight instance graphs, GW rounding would give an $\alpha_{GW}$ approximation (by design), and the predicted cut would give $\approx 0.5/(0.845) \ll \alpha_{GW}$ approximation. 

- *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.[..] What are your thoughts on this way of viewing the prediction in the context of your problem?*

Such a model would certainly make sense, but the qualitative bounds would depend on the instances. In particular, without additional assumptions, giving the adversary power to choose the partition can make the predictions useless despite being correct on almost all the vertices. For example, consider an instance containing $(1-\delta)n$ isolated vertices, and an arbitrary “hard” graph on the remaining $\delta n$ vertices. Now the adversary may only provide correct predictions on those isolated vertices.

So, we need to make some assumptions to avoid these pathologies. For example, if we assume that the graph is regular, our Theorem 4.1 for partial predictions that gives $0.858 + \Omega(\epsilon)$ approximation goes through even with deterministic predictions. A similar result holds in general graphs for deterministic predictions satisfying other properties. E.g., if an $\epsilon$ fraction of neighbors’ labels are revealed for every vertex, or more generally, if an $\epsilon$ fraction of edges are incident to the vertices whose labels are revealed. We will include a discussion about deterministic predictions in the Closing Remarks. We hope that our work will spur future investigation into such prediction models.

- *As 𝜖→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? […]*

Our algorithms indeed achieve a near-perfect approximation as the advice becomes nearly perfect. For the noisy model, when $\epsilon=1/2 - \delta$ for small $\delta>0$, it can be shown that a simplification of our algorithm in Section 3.1 guarantees an $(1-O(\sqrt(\delta)))$-approximation. The simplification is just ignoring $\Delta$ and $\eta$, wideness and prefixes, and letting $\tilde{A} = A$. Then Lemma 3.5 can be shown to hold with the the right hand side replaced by $O(\sqrt{\delta} W)$, where the crucial change in the proof is the upper bound on $Var(Z_j)$ in line 220 from $O(1/\epsilon^2)$ to $O(\delta)$.

For the partial prediction model, when $\epsilon = 1-\delta$ for small $\delta>0$, Theorem 4.2’s guarantee $\alpha_{RT} + (1 - \alpha_{RT} - o(1))(2\epsilon - \epsilon^2)$ becomes $1 - O(\delta^2)$.

We will try to mention the above results in the final version of the paper. 

- *What is the intuition for why predictions are not needed for narrow instances?*

For this discussion, consider unweighted graphs. Algorithms improving on GW for low-degree graphs use two ideas: a stronger SDP relaxation using triangle inequalities, and a local search after rounding. The GW SDP has a tight integrality gap even on degree-2 instances, so using the stronger SDP is unavoidable. 
*Why does local search help on low-degree graphs?* Well, for high-degree vertices, tail concentration typically forces each vertex to have more neighbors on the other side of the cut after rounding. But this is not the case for low-degree graphs because concentration bounds are weaker, which means that locally improving moves is a viable strategy for improving the rounded solution with non-trivial probability. For a longer discussion, please see the paper of Feige, Karpinski, and Langberg that gave the first algorithm to beat the GW bound on low-degree graphs. 

For weighted graphs, all this intuition carries over, but we need to be careful how the weight of the edges incident to a vertex are distributed: whether it is concentrated on a few edges (“narrow”) or is spread over many edges (“wide”). (We will add the intuition in the next version of the paper.)
We thank the reviewer for the comments and constructive encouragement.

- *Could you please motivate more about the advantages of utilizing predictions in the offline setting with practical applications?*

Predictions in both the offline and online settings help overcome worst-case outcomes by providing additional information about a specific instance. In the offline setting, predictions help bypass computational lower bounds as against information-theoretic ones online. In practice, predictions for offline problems model different scenarios; we list three examples here: 
They can be generated by machine learning models based on solving similar instances previously. This is common for applications such as revenue optimization in auctions.
They can be used to model advice received from domain experts. 
They can be used to model settings in which a first, coarse solution has already been computed. An algorithm can take advantage of this information to provide a “warm start” without repeating the possibly expensive computation.

- *How does your setup differ from the works of [Bampis et al., 2024] and [Ghoshal et al., 2024]?*

The parallel work of [Bampis et al] considers dense instances of certain maximization problems, including max-cut. Their notion of dense instances have $\Omega(n^2)$ edges (whereas our max-cut results are for general instances). This high density allows them to use advice from only a poly-logarithmic number of calls to the oracle. Moreover, their focus is improving the running time of the PTAS algorithms, whereas our focus is on getting improvements to the approximation guarantees.

The independent and unpublished work of [Ghoshal et al.] considers a model very similar to ours. The original version of their work (concurrent to ours) considered dense cases of max-cut and the closely related max-2LIN. Their notion of density is much weaker than Bampis et al, and is similar to our notion of wide instances. A more recent version (subsequent to ours, and uploaded last week) of their paper gives algorithms for dense instances of 3LIN (and hardness for 4LIN), in contrast to our work that goes in the direction of exploring more general 2CSPs. 

- *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?*

The computational hardness of Max-Cut (in particular the Unique-Games hardness) means that any polynomial-time approximation algorithm would have an approximation guarantee no better than $\alpha_{GW}$. Hence, we cannot restrict the algorithm to polynomial computation in a standard sense. It would definitely be interesting to consider a model with “parsimonious predictions” where we count the number of queries (say $Q$) made to the prediction oracle, and then study the approximation factor as a function of both the parameter $\varepsilon$ and $Q$. Note that since we are counting calls to an oracle instead of computation time, the hardness results for polynomial-time algorithms are no longer relevant in this setting. The parallel work of Bampis et al. considers parsimonious predictions for dense instances of max-cut with quadratically many edges, and it may also be interesting to consider it for general instances; this seems like a cool direction to explore!