2026-09-08T01:22:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26500 2026-09-05T19:45:25Z ddc:004 open_access

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut Huang, Jeremy Ahrens Ko, Young Kun Wang, Chunhao fine-grained complexity instance compression quantum algorithms approximation algorithms CVP Max-Cut Min-UnCut Max-2-Lin approximation-preserving reductions We show a linear-size reduction from gap Max-2-Lin(2) (a generalization of the approximate Maximum Cut, or gap Max-Cut, problem) to γ-CVP_p for γ = O(1) and finite p ≥ 1, as well as a no-go theorem against poly-sized non-adaptive quantum reductions from k-SAT to CVP₂. This implies three headline results: (i) Faster algorithms for γ-CVP_p are also faster algorithms for Max-2-Lin(2) and Max-Cut. Depending on the approximation regime, even a 2^{0.78n}-time or 2^{0.3n}-time algorithm would improve upon state-of-the-art algorithms such as Williams' 2004 algorithm [TCS 2005] or Arora, Barak, and Steurer’s 2010 algorithm [JACM 2015]. This provides evidence that γ-CVP_p for γ = O(1) requires exponential time, improving upon the previous exponential lower-bound for γ-CVP₂ with γ < 3 by Bennett, Golovnev, and Stephens-Davidowitz [FOCS 2017]. (ii) A new almost 2^{(1/2 + ε/4ς + o(1)) n}-time classical algorithm and a new almost 2^{(1/3 + ε/6ς + o(1)) n}-time quantum algorithm for (1-ε, 1-ς)-gap Max-Cut. This algorithm is faster than the algorithm of Arora, Barak and Steurer [JACM 2015], as well as the algorithm of Williams [TCS 2005], and the algorithm of Manurangsi and Trevisan [APPROX 2018] when c₀ ε < ς < c₁ ε for constants c₀, c₁. (iii) If the Quantum Strong Exponential Time Hypothesis (QSETH) can be used to show a 2^{δ n}-time lower-bound for Max-Cut, Max-2-Lin(2), or CVP₂ for any constant δ > 0, it must be via an adaptive quantum reduction unless NP ⊆ pr-QSZK. This illuminates some difficulties in characterizing the hardness of approximate constraint satisfaction problems and shows that the post-quantum security of lattice-based cryptography likely cannot be supported by QSETH. This result complements the no-go results of Aggarwal and Kumar [FOCS 2023], who showed that the classical security of lattice-based cryptography likely cannot be supported by the classical Strong Exponential Time Hypothesis (SETH). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeremy Ahrens Huang and Young Kun Ko and Chunhao Wang 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.111 urn:nbn:de:0030-drops-265001 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.111 eng https://creativecommons.org/licenses/by/4.0/legalcode