Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with k-sum:
TR17-082 | 4th May 2017
Daniel Kane, Shachar Lovett, Shay Moran

Near-optimal linear decision trees for k-SUM and related problems

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.
For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries.
Moreover, the queries we use are comparison ... more >>>

ISSN 1433-8092 | Imprint