7
$\begingroup$

Ezra and Sharir showed the $O(n^2\log^2 n)$ linear decision tree complexity for $k$-SUM problem [1], which improves the $O(n^3\log^3 n)$ complexity result of Cardinal et al [2].

It is known that $k$-SUM and Table-$k$-SUM problems are related and can be reduced to each other in linear time[3] and both problems can be solved in polynomial time $O(m^k).$

$\textbf{$k$-SUM Conjecture}$ [4]: There does not exist a $k ≥ 2$, an $ε > 0$, and a randomized algorithm that succeeds (with high probability) in solving $k$-SUM in time $O(n^{ \left \lceil{k/2}\right \rceil−ε})$.

What's the consequence of the above new decision tree complexity results? What can this lead to a new bound for the time complexity of $k$-SUM problem?

[1] Ezra, Esther, and Micha Sharir. "The Decision Tree Complexity for $ k $-SUM is at most Nearly Quadratic." arXiv preprint arXiv:1607.04336 (2016).

[2] Cardinal, Jean, John Iacono, and Aurélien Ooms. "Solving $ k $-SUM using few linear queries." arXiv preprint arXiv:1512.06678 (2015).

[3] Woeginger, Gerhard J. "Space and time complexity of exact algorithms: Some open problems." International Workshop on Parameterized and Exact Computation. Springer Berlin Heidelberg, 2004.

[4] Abboud, Amir, and Kevin Lewi. "Exact weight subgraphs and the k-sum conjecture." International Colloquium on Automata, Languages, and Programming. Springer Berlin Heidelberg, 2013.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.