This paper has been withdrawn by Ali Çivril

[Submitted on 9 May 2023 (v1), last revised 21 Jul 2026 (this version, v3)]

No PDF available, click to view other formats

Abstract:We provide a new approach for establishing hardness of approximation results, based on the theory recently introduced by the author. It allows one to directly show that approximating a problem beyond a certain threshold requires super-polynomial time. To exhibit the framework, we revisit two famous problems in this paper. The particular results we prove are:
MAX-3-SAT$(1,\frac{7}{8}+\epsilon)$ requires exponential time for any constant $\epsilon$ satisfying $\frac{1}{8} \geq \epsilon > 0$. In particular, the gap exponential time hypothesis (Gap-ETH) holds.
MAX-3-LIN-2$(1-\epsilon, \frac{1}{2}+\epsilon)$ requires exponential time for any constant $\epsilon$ satisfying $\frac{1}{4} \geq \epsilon > 0$.

Submission history

From: Ali Çivril [view email]
[v1] Tue, 9 May 2023 13:09:42 UTC (8 KB)
[v2] Thu, 22 Feb 2024 08:05:47 UTC (8 KB)
[v3] Tue, 21 Jul 2026 09:08:33 UTC (1 KB) (withdrawn)