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 1


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.

  • 3
    $\begingroup$ Do you mean that $\alpha$ is strictly increasing, or at least goes to infinity? $\endgroup$ Apr 30, 2019 at 5:46
  • $\begingroup$ @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? $\endgroup$
    – Turbo
    May 1, 2019 at 3:29
  • $\begingroup$ Added "unbounded" :) $\endgroup$ May 11, 2019 at 5:15
  • $\begingroup$ @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 $\endgroup$ May 11, 2019 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.