Adversary Lower Bound for Element Distinctness

2012/04/23 by Aleksandrs Belovs, Belovs, Aleksandrs · 1 citation
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph

paper · pdf · doi:10.48550/arxiv.1204.5074

6 pages

arxiv created 2012/04/23 · arxiv updated 2012/04/24

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.

Cited by

• Adversary Lower Bound for the k-sum Problem

Related

• Adversary Lower Bound for Element Distinctness with Small Range
• The General Adversary Bound: A Survey
• Adversary Lower Bound for the Orthogonal Array Problem
• Adversary Lower Bounds for the Collision and the Set Equality Problems
• Sample complexity of the distinct elements problem