# 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?

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? – Turbo May 1 at 3:29