10
$\begingroup$

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?

$\endgroup$
16
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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