Adversary Lower Bound for Element Distinctness [PDF]
Aleksandrs BelovsIn 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.View original: http://arxiv.org/abs/1204.5074
No comments:
Post a Comment