Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > K-SUM:
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 >>>

TR21-152 | 8th November 2021
Gal Arnon, Tomer Grossman

#### Min-Entropic Optimality

We introduce the notion of \emph{Min-Entropic Optimality} thereby providing a framework for arguing that a given algorithm computes a function better than any other algorithm. An algorithm is $k(n)$ Min-Entropic Optimal if for every distribution $D$ with min-entropy at least $k(n)$, its expected running time when its input is drawn ... more >>>

ISSN 1433-8092 | Imprint