# An obstruction like ETH

We know under $$ETH$$ we cannot solve $$K$$-SUM in $$f(K)poly(nK)$$ time under any function $$f(K)$$ (usually $$2^{O(K)}$$).

Is there any conjecture that prevents a $$(\log n)^{O(K)}$$ complexity (this is entirely consistent with possibility as $$K=\Omega(n)$$ we need exponential time for subset sum) or is such possibility allowed?

## 1 Answer

ETH itself precludes this possibility.

In https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf we show that any $$n^{O(1)} n^{k/\alpha(k)}$$ time algorithm for k-SUM, for any monotone nondecreasing unbounded function $$\alpha$$, would imply ETH is false.

• Do you mean that $\alpha$ is strictly increasing, or at least goes to infinity? – Sasho Nikolov Apr 30 at 5:46
• @RyanWilliams Similar in spirit to ETH like obstruction. Is there anything that would prevent $O((\log n)^{O(k)})$ complexity with polynomial size advice or a PPAD oracle? – T.... May 1 at 3:29
• Added "unbounded" :) – Ryan Williams May 11 at 5:15
• @Brout Note that (log(n))^k is an FPT function, so yeah, ETH rules that out. With poly size advice it would mean subexponential size circuits for 3sat. With a PPAD oracle it would seem to imply that ETH implies PPAD not in P. To me that would be a breakthrough, I don't know of much corroborating evidence that PPAD isn't in P – Ryan Williams May 11 at 5:19