{"id":"arxiv/2610.25047","url":"https://arxiv.org/abs/2610.25047","tags":["cs.DS","cs.CC","math.CO"],"score":0,"title":"Approximating Independent Sets Using Additive Combinatorics","domain":"cs.DS","source":"arxiv","authors":["Shachar Lovett"],"reviews":0,"subject":"cs.DS","summary":"We give a deterministic quasi-polynomial time algorithm for approximating the largest independent set in a graph. We show that if an $N$-vertex graph contains an independent set of size $2^{-t} N$, then we can find an independent set of size $2^t$ in quasi-polynomial time, for all $t$ up to a constant factor of $(\\log N)^{1/3}$. This gives an approximation factor of $N / \\exp((\\log N)^{1/3})$, which has the same shape as known hardness results for quasi-polynomial time algorithms, up to a different exponent of the logarithm. The algorithm builds on a structural principle: a graph containing…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-18","reactions":{}}