{"id":"100e3777-cc4d-4b66-bd46-367c47511220","arxiv_id":"2302.08118","paper_version":3,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Introduces a commutativity-based generic technique for instance-specific linear relaxations of SDPs, with proofs of stronger bounds for max-cut and experimental validation on several problem families.","lead":"The paper introduces a technique to derive linear relaxations of semidefinite programs using commutativity between constraint and objective matrices, with applications to max-cut and Lovasz theta. This could support more efficient optimization algorithms by providing polyhedral approximations for warm-starting SDP solvers.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"Commutativity of objective and constraint matrices is required for the matching guarantees and may not hold broadly enough for the relaxed methodology to be generally effective.","rationale":"The reader's weakest_assumption correctly isolates the dependency on commutativity being exploitable. Because the full text was not reviewed by the reader, the concrete_test above directly verifies whether that dependency is satisfied on the paper's own experimental instances, which would either confirm or refute the load-bearing assumption without requiring external data.","tokens_in":1750,"tokens_out":388,"duration_ms":15630,"concrete_test":"For the max-cut SDP formulation in §4, take the 20 largest Gset instances used in the experiments; explicitly compute the commutator [C, A_i] for the objective matrix C and each diagonal constraint matrix A_i; report the fraction of instances where all commutators are numerically zero (within 1e-10). If the fraction is below 30%, re-run the LP vs. SDP comparison on the non-commuting subset to check whether the claimed strengthening of the eigenvalue bound still holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central technique derives linear relaxations with provable guarantees only when the objective matrix commutes with the constraint matrices (allowing simultaneous diagonalization and exact value matching). The paper then relaxes this exact-matching condition to a 'flexible methodology' for 'effective' approximations, but provides no general proof that the relaxed version retains approximation quality without commutativity. Specializations to max-cut (Poljak-Rendl SDP) and Lovász theta claim the resulting LP certifies and strengthens the eigenvalue bound, yet this still presupposes that the relevant matrices in those formulations commute or can be chosen to do so on the instances considered. If commutativity fails on typical instances of the target problem classes, the instance-specific claim reduces to a narrow special case with limited practical scope.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript introduces a generic technique to obtain linear relaxations of semidefinite programs (SDPs) with provable guarantees based on commutativity of the objective and constraint matrices. It studies conditions for exact matching of optimal values between the SDP and the linear relaxation, relaxes these conditions to a flexible methodology for effective approximations, specializes the results to the Poljak-Rendl SDP for max-cut and the Lovász theta number, proves that the proposed max-cut LP certifies and strengthens a known eigenvalue bound, and demonstrates the use of the LPs to warm-start iterative polyhedral approximations of SDPs through experiments on max-cut, Lovász theta, and QCQP relaxations.","tokens_in":1923,"tokens_out":568,"duration_ms":23674,"significance":"If the claims hold, the work offers a concrete method for generating instance-specific linear programs that approximate certain SDPs, with a notable strengthening result for the max-cut eigenvalue bound and practical value for warm-starting SDP solvers. The specialization to max-cut and the experimental verification on multiple problem families are strengths; the approach could be useful in optimization if the relaxed methodology retains effectiveness beyond strictly commuting cases.","major_comments":[{"comment":"§3 (relaxation of matching condition): The paper relaxes the exact commutativity-based matching condition to a 'flexible methodology' for effective linear relaxations but provides no general quantitative bound or guarantee on approximation quality when the objective and constraint matrices do not commute; this is load-bearing for the central claim that the technique yields effective approximations for the target problem classes (max-cut, Lovász theta, QCQPs).","section":"§3"},{"comment":"§5 (max-cut specialization): The proof that the proposed LP certifies the eigenvalue bound and is strictly stronger relies on the Poljak-Rendl formulation matrices permitting simultaneous diagonalization; the manuscript does not clarify whether this holds for arbitrary max-cut instances or only selected ones, which directly affects the scope of the strengthening claim.","section":"§5"}],"minor_comments":[{"comment":"The notation for the instance-specific linear relaxation (e.g., how the diagonalization is applied per instance) could be made more explicit to aid reproducibility.","section":"Notation throughout"},{"comment":"Table or figure captions in the experimental section would benefit from explicit mention of the number of instances and how commutativity was verified or assumed.","section":"Experimental section"}],"recommendation":"major_revision","confidential_remarks":"The manuscript positions itself well within math.OC but could more explicitly contrast the instance-specific commutativity approach against existing general-purpose polyhedral outer-approximation schemes for SDPs in the introduction."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below, indicating revisions where appropriate.","responses":[{"response":"We acknowledge that the manuscript provides no general quantitative bound on approximation quality for non-commuting cases. The exact matching result requires commutativity, while the flexible methodology is offered as a practical heuristic whose effectiveness is supported by the experimental results on max-cut, Lovász theta, and QCQP instances. The central theoretical claims remain tied to the commuting case; the experiments serve to illustrate utility beyond that case. We will revise §3 to explicitly note the absence of general bounds and the reliance on empirical validation for the non-commuting regime.","revision_made":"yes","referee_comment":"[§3] §3 (relaxation of matching condition): The paper relaxes the exact commutativity-based matching condition to a 'flexible methodology' for effective linear relaxations but provides no general quantitative bound or guarantee on approximation quality when the objective and constraint matrices do not commute; this is load-bearing for the central claim that the technique yields effective approximations for the target problem classes (max-cut, Lovász theta, QCQPs)."},{"response":"The Poljak-Rendl SDP formulation has the structural property that its objective and constraint matrices permit simultaneous diagonalization for every max-cut instance, independent of the underlying graph. This follows from the diagonal nature of the equality constraints together with the form of the objective matrix (derived from the graph Laplacian). The strengthening result therefore applies to arbitrary instances. We will add an explicit statement and brief justification of this fact in the revised §5.","revision_made":"yes","referee_comment":"[§5] §5 (max-cut specialization): The proof that the proposed LP certifies the eigenvalue bound and is strictly stronger relies on the Poljak-Rendl formulation matrices permitting simultaneous diagonalization; the manuscript does not clarify whether this holds for arbitrary max-cut instances or only selected ones, which directly affects the scope of the strengthening claim."}],"tokens_in":1379,"tokens_out":442,"duration_ms":16826,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main thing to know is that this paper ties linear relaxations of SDPs to commutativity of the objective and constraint matrices, which lets them match the SDP value exactly via simultaneous diagonalization. They then loosen the exact condition into a flexible method and specialize it to the Poljak-Rendl max-cut SDP and Lovasz theta, proving the resulting LP certifies and strengthens the eigenvalue bound for max-cut. Experiments show the LPs can warm-start SDP solvers on those problems plus some QCQP relaxations. That max-cut strengthening and the warm-start tests are the concrete parts that work. The new element is the commutativity-based generic technique plus the matching conditions; it is not just a restatement of prior SDP theory. The approach stays grounded in standard results on simultaneous diagonalization and does not invent new entities. The soft spot is the step after relaxing the exact-matching condition. The paper does not supply a general proof that the flexible methodology keeps useful approximation quality when commutativity fails, which the stress-test note correctly flags. If commuting matrices are uncommon outside the chosen families, the instance-specific claim narrows to special cases rather than a broadly effective tool. The experiments are helpful but do not test how often the property holds on random instances. This is for people working on SDP outer approximations or initialization for max-cut, graph partitioning, or QCQPs. The math and citation pattern look solid on the max-cut result, and the work shows clear engagement with the literature. It deserves a serious referee to check the general guarantees and the scope of the relaxed method.","headline":"Commutativity gives exact SDP-LP value matching and a stronger max-cut LP than the eigenvalue bound, but the relaxed general methodology lacks broad guarantees when matrices do not commute.","tokens_in":2383,"tokens_out":392,"would_cite":false,"duration_ms":17912,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"Commutativity-based SDP-to-LP relaxations via simultaneous diagonalization share no machinery with RS forcing from distinction","alignment":"orthogonal","rationale":"Paper centers on Theorems 1-3 and Observation 2: commutativity of {C, Ai} yields polyhedral dual Γ and exact LP solvability under oracle O (simultaneous diagonalization, eigenvector bases S = E(C - A(y))). Specializes to max-cut eigenvalue bound χ(G) = -n λ_n(W) and Lovász theta. RS derives J(x) = ½(x + x⁻¹) - 1, φ, 8-tick period, D=3 from single distinction (reality_from_one_distinction, AbsoluteFloorClosure, Cost/FunctionalEquation washburn_uniqueness_aczel, AlexanderDuality). No ratio symmetry, J-cost, φ-ladder or 8-period structures appear; domain is standard convex optimization with no overlap or contradiction.","tokens_in":61914,"confidence":"high","tokens_out":213,"duration_ms":6369,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Commutativity of matrices allows construction of linear relaxations for semidefinite programs that match the SDP optimum under stated conditions and strengthen known bounds for max-cut.","keywords":["linear relaxations","semidefinite programming","max-cut","Lovasz theta","commutativity","polyhedral approximation","quadratic constraints"],"falsifier":"An explicit max-cut SDP instance on which the proposed linear program returns a strictly smaller upper bound than the eigenvalue bound would disprove the strengthening claim.","tokens_in":2659,"feed_emoji":"","tokens_out":722,"duration_ms":17925,"temperature":0.7,"pith_summary":"The paper presents a technique that converts semidefinite programs into linear programs by using the commutativity of the objective matrix and the constraint matrices. It first gives conditions under which the two problems attain the same optimal value, then relaxes those conditions to obtain practical linear programs that still carry approximation guarantees. The method is applied to the Poljak-Rendl SDP for max-cut, where the resulting linear program certifies the standard eigenvalue bound and improves on it, and to the Lovasz theta number. The linear programs can also initialize iterative polyhedral methods that solve the original SDPs. The work matters because many combinatorial and quadratic problems admit SDP relaxations whose size limits direct solution, while the derived linear programs remain tractable yet retain useful tightness.","feed_headline":"Commutativity turns some SDPs into linear programs","feed_subtitle":"The resulting LPs match SDP values when matrices commute and strengthen the eigenvalue bound for max-cut while enabling warm-starts.","key_machinery":"Commutativity between the objective matrix and the linear constraint matrices of the SDP, which reduces the semidefinite feasible set to a polyhedral set whose optimum matches or approximates the SDP value.","core_discovery":"A generic technique obtains linear relaxations of semidefinite programs with provable guarantees from the commutativity of the constraint and objective matrices; exact agreement between the SDP and linear relaxation holds under identified eigenvector conditions, which can then be relaxed while preserving effective bounds; specialization to the max-cut SDP produces a linear program that both certifies and exceeds the known eigenvalue bound, and the same ideas generate linear programs for the Lovasz theta number and for convex relaxations of quadratically constrained quadratic programs.","pith_inferences":["If exact commutativity is infrequent, one could search for nearby commuting bases or low-rank projections to retain instance-specific linear relaxations.","The technique might apply to other SDP relaxations in combinatorial optimization such as graph partitioning or quadratic assignment.","Empirical success on moderate-sized instances suggests the linear programs could replace SDP solves in branch-and-bound frameworks when only bounds are needed."],"forward_implications":["The linear program for max-cut is at least as strong as the eigenvalue bound and strictly stronger on some instances.","The same construction yields a linear program for the Lovasz theta number.","The linear programs serve as warm-starts for polyhedral approximation algorithms solving the original SDPs.","The approach extends to three families of SDPs arising as convex relaxations of quadratically constrained quadratic programs."],"fun_headline_variants":[],"cache_read_input_tokens":2112,"weakest_assumption_plain":"Commutativity (or a usable relaxation of it) occurs often enough in the SDPs for max-cut, Lovasz theta, and QCQP relaxations that the derived linear programs remain tight.","fun_headline_variants_meta":{"error":"Extra data: line 10 column 1 (char 225)"},"cache_creation_input_tokens":0},"created_at":"2026-05-24T10:02:03.622608+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit max-cut SDP instance on which the proposed linear program returns a strictly smaller upper bound than the eigenvalue bound would disprove the strengthening claim.","supporting_citations":[],"review_version":1}