Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k
cs.CC
Submitted: 2026-11-01
Updated: 2026-11-01
Terminology
Sources
- New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
- Improved Inapproximability Results for Maximum k-Colorable Subgraph
- Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT
- AlphaEvolve: A coding agent for scientific and algorithmic discovery
- Reinforced Generation of Combinatorial Structures: Hardness of Approximation
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?