Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ELEMENT DISTINCTNESS:
Reports tagged with Element Distinctness:
TR99-020 | 9th June 1999
Marek Karpinski

#### Randomized Complexity of Linear Arrangements and Polyhedra

We survey some of the recent results on the complexity of recognizing
n-dimensional linear arrangements and convex polyhedra by randomized
algebraic decision trees. We give also a number of concrete applications
of these results. In particular, we derive first nontrivial, in fact

TR13-127 | 15th September 2013
Paul Beame, Raphael Clifford, Widad Machmouchi

#### Element Distinctness, Frequency Moments, and Sliding Windows

We derive new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistics, that are simple to calculate for sorted data. In particular, we develop a randomized algorithm for the element distinctness problem whose time $T$ and space $S$ ... more >>>

TR15-041 | 25th March 2015
Mark Bun, Justin Thaler

#### Dual Polynomials for Collision and Element Distinctness

The approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within error $1/3$ in the $\ell_\infty$ norm. In an influential result, Aaronson and Shi (J. ACM 2004) proved tight $\tilde{\Omega}(n^{1/3})$ and $\tilde{\Omega}(n^{2/3})$ lower bounds on ... more >>>

ISSN 1433-8092 | Imprint