arxiv: 2602.20376 · v2 · submitted 2026-02-23 · 💻 cs.DS · cs.LG· math.OC· quant-ph

Recognition: 2 theorem links

· Lean Theorem

Exploiting Low-Rank Structure in Max-K-Cut Problems

Ria Stevens , Fangshuo Liao , Barbara Su , Jianqiang Li , Anastasios Kyrillidis

Authors on Pith no claims yet

Pith reviewed 2026-05-15 19:41 UTC · model grok-4.3

classification 💻 cs.DS cs.LGmath.OCquant-ph

keywords Max-3-Cutlow-rank matrixcomplex quadratic formcandidate enumerationgraph partitioningcombinatorial optimizationapproximation algorithm

0 comments

The pith

Low-rank structure in the Max-3-Cut objective guarantees that a set of O(n^{2r-1}) candidates contains the exact maximizer.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that Max-3-Cut can be recast as the maximization of a complex-valued quadratic form, and that low-rank structure in the objective matrix permits an algorithm to enumerate a modest number of candidate vectors whose best member is provably optimal. This yields a family of parallelizable procedures that avoid the computational cost of classical semidefinite programming while retaining exactness when the rank is small. A reader would care because the approach scales to larger graphs than SDP solvers typically handle and still matches their practical performance on benchmark instances.

Core claim

When the objective matrix of a Max-3-Cut instance admits a rank-r factorization, the global maximizer of the associated complex quadratic form is guaranteed to lie among a explicitly constructible collection of O(n^{2r-1}) candidate assignments; the same enumeration supplies approximation guarantees once the matrix is only a perturbation of a low-rank matrix.

What carries the argument

Enumeration of O(n^{2r-1}) candidate solutions obtained from the low-rank factorization of the complex quadratic objective matrix.

If this is right

For any fixed rank r the running time is polynomial in the number of vertices n.
The same candidate list yields provable approximation ratios when the objective is a small perturbation of a low-rank matrix.
The enumeration step is embarrassingly parallel, allowing straightforward distribution across processors.
On standard graph benchmarks the method produces solutions whose quality is statistically indistinguishable from SDP-based heuristics while using less memory.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The technique may generalize to other K values if analogous complex or higher-order reformulations can be found.
Graphs whose adjacency or Laplacian matrices are observed to be approximately low-rank in practice become natural targets for exact recovery via this route.
The candidate-generation procedure could be combined with branch-and-bound or local search to handle instances that are only partially low-rank.

Load-bearing premise

The Max-3-Cut objective must be exactly captured by a low-rank complex quadratic form with no additional modeling discrepancy.

What would settle it

A concrete low-rank objective matrix together with an optimal assignment that lies outside the enumerated candidate set.

read the original abstract

We approach the Max-3-Cut problem through the lens of maximizing complex-valued quadratic forms and demonstrate that low-rank structure in the objective matrix can be exploited, leading to alternative algorithms to classical semidefinite programming (SDP) relaxations and heuristic techniques. We propose an algorithm for maximizing these quadratic forms over a domain of size $K$ that enumerates and evaluates a set of $O\left(n^{2r-1}\right)$ candidate solutions, where $n$ is the dimension of the matrix and $r$ represents the rank of an approximation of the objective. We prove that this candidate set is guaranteed to include the exact maximizer when $K=3$ (corresponding to Max-3-Cut) and the objective is low-rank, and provide approximation guarantees when the objective is a perturbation of a low-rank matrix. This construction results in a family of novel, inherently parallelizable and theoretically-motivated algorithms for Max-3-Cut. Extensive experimental results demonstrate that our approach achieves performance comparable to existing algorithms across a wide range of graphs, while being highly scalable.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives an exact enumeration algorithm for low-rank Max-3-Cut that checks O(n^{2r-1}) candidates and is proven to contain the optimum.

read the letter

The paper's core contribution is an algorithm that, for low-rank Max-3-Cut instances, enumerates O(n^{2r-1}) candidate solutions and is proven to include the exact optimum. This comes from maximizing a complex quadratic form using the standard cube-root-of-unity embedding for the three partitions. What stands out is the exactness guarantee tied directly to the rank. For matrices that are exactly rank r, the method finds the global max without relying on SDP relaxations or heuristics. The perturbation bounds for near-low-rank cases are a reasonable extension, showing how the error scales with the approximation quality. Experiments indicate it performs on par with existing solvers while being more scalable in some regimes, which is useful for larger graphs where SDP might struggle with memory or time. The approach is parallelizable by design since candidates can be evaluated independently, which could matter for large n. The citation pattern seems standard for the area, pulling from SDP literature and Max-Cut approximations without obvious omissions. On the downside, the runtime depends heavily on r. Even for moderate ranks like 5 or 6, n^9 or n^11 quickly becomes impractical unless r is very small or n is modest. The paper assumes the objective either has low rank or can be well-approximated by one, but real-world graphs often don't satisfy this cleanly, so the practical scope might be narrower than the abstract suggests. The stress test notes no internal gaps, but the full derivation would need checking for how the candidates are generated efficiently. This work is aimed at researchers in discrete optimization who want alternatives to SDP for structured instances of Max-Cut. A reader interested in algebraic or low-rank techniques for combinatorial problems would get value from the exactness result and the complexity bound. I would send it for peer review. The theoretical claim is sharp enough to warrant checking the details, even if the experiments are mostly comparative and the impact is specialized.

Referee Report

2 major / 2 minor

Summary. The paper approaches Max-3-Cut via maximization of complex-valued quadratic forms using cube roots of unity. For an objective matrix of rank r it enumerates a candidate set of size O(n^{2r-1}), proves that this set contains the exact maximizer when the matrix is exactly low-rank, supplies approximation guarantees when the matrix is a perturbation of a low-rank matrix, and reports experimental performance comparable to SDP-based and heuristic solvers with improved scalability and inherent parallelizability.

Significance. If the central enumeration theorem holds, the work supplies a theoretically grounded, polynomial-time exact algorithm for fixed r on low-rank Max-3-Cut instances together with approximation bounds for near-low-rank cases. This constitutes a concrete alternative to SDP relaxations whose cubic scaling is avoided when r is small, and the parallelizable candidate evaluation is a practical strength for structured graphs.

major comments (2)

[Proof of candidate-set completeness] The proof that the O(n^{2r-1}) candidate set is guaranteed to contain the exact maximizer (K=3, exact rank r) is the load-bearing claim; the argument must be checked for completeness with respect to the complex embedding and the enumeration strategy over the low-rank factorization.
[Perturbation guarantees] The perturbation analysis states approximation guarantees but does not quantify the dependence of the additive error on the Frobenius (or spectral) norm of the perturbation relative to the rank-r approximation error; this bound is needed to assess practical utility.

minor comments (2)

[Algorithm description] Clarify the precise per-candidate evaluation cost (including the quadratic-form computation) so that the overall time complexity is stated explicitly.
[Experiments] In the experimental section, report the method used to obtain the rank-r approximation of the objective matrix and the range of r values tested on each graph family.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment, the recognition of the practical strengths of the enumeration approach, and the recommendation for minor revision. We address each major comment below and will incorporate clarifications and explicit bounds in the revised manuscript.

read point-by-point responses

Referee: [Proof of candidate-set completeness] The proof that the O(n^{2r-1}) candidate set is guaranteed to contain the exact maximizer (K=3, exact rank r) is the load-bearing claim; the argument must be checked for completeness with respect to the complex embedding and the enumeration strategy over the low-rank factorization.

Authors: The completeness argument relies on the fact that any maximizer of the complex quadratic form, when the matrix admits a rank-r factorization, can be recovered by assigning each of the r factors independently to one of the three cube roots of unity and then enumerating the resulting O(n^{2r-1}) linear combinations; the group structure of the cube roots ensures that all discrete K=3 assignments are covered. We have re-verified that the embedding and factorization steps are fully accounted for in the existing proof. To improve readability and address the referee's request for explicit checking, the revised manuscript will include an expanded derivation with an additional lemma that isolates the enumeration over the low-rank factors. revision: partial
Referee: [Perturbation guarantees] The perturbation analysis states approximation guarantees but does not quantify the dependence of the additive error on the Frobenius (or spectral) norm of the perturbation relative to the rank-r approximation error; this bound is needed to assess practical utility.

Authors: We agree that an explicit dependence improves the utility statement. The current analysis already shows that the additive error is controlled by the size of the perturbation relative to the best rank-r approximation; we will make this dependence concrete by stating that the error is at most O(‖E‖_F ⋅ n) (or the analogous spectral-norm version), where E denotes the perturbation matrix. This explicit form will be added to the theorem statement and its proof in the revision. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's core contribution is a mathematical proof establishing that an enumerated candidate set of size O(n^{2r-1}) contains the exact maximizer of the complex quadratic form for exact low-rank objectives when K=3. This relies on the standard cube-roots-of-unity embedding for Max-3-Cut (an external reduction with no modeling error) and algebraic properties of low-rank matrices, without any fitted parameters, self-definitional loops, or load-bearing self-citations. Perturbation guarantees are stated separately and do not reduce to the main claim. The derivation is self-contained against external benchmarks and does not rename known results or smuggle ansatzes.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach relies on standard linear-algebra facts about low-rank matrices and quadratic forms; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract description.

axioms (1)

standard math Low-rank matrices admit useful approximations and their quadratic forms can be maximized by enumeration over a polynomial-sized candidate set
Invoked to justify the O(n^{2r-1}) enumeration and exactness claim; standard in linear algebra and optimization.

pith-pipeline@v0.9.0 · 5507 in / 1286 out tokens · 44130 ms · 2026-05-15T19:41:43.121613+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking (D=3 forcing) unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove that this candidate set is guaranteed to include the exact maximizer when K=3 ... enumerates and evaluates a set of O(n^{2r-1}) candidate solutions
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel (J-cost uniqueness) unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

max z† Q z over z in A_K^n (K-th roots of unity); decision boundaries ϑ_m = π(2m+1)/K

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.