Adversary Lower Bound for Element Distinctness
arXiv:1204.5074
Abstract
In this note we construct an explicit optimal (negative-weight) adversary matrix for the element distinctness problem, given that the size of the alphabet is sufficiently large.
arXiv comment6 pages