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.


Your Answer

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