@inproceedings{22915,
  abstract     = {The element distinctness problem takes as input a list I of n values from a totally ordered universe, where pairwise comparisons between values are allowed, and the goal is to decide whether I contains any duplicates. It is a well-studied problem with a classical worst-case Ω(n log n) comparison-based lower bound by Fredman [TCS'76]. At first glance, this lower bound appears to rule out any algorithm more efficient than the naive approach of sorting I and comparing adjacent elements. However, upon closer inspection, the Ω(n log n) bound is overly pessimistic. For instance, if I contains n/2 identical elements, a median-finding algorithm will, regardless of the input order, find a duplicate in linear time. This raises a natural question: Are there comparison-based lower bounds for element distinctness that are sensitive to the amount of duplicates in the input instance?
To address this question, we derive instance-specific lower bounds. For any input instance I, we represent the combinatorial structure of the duplicates in I by an undirected graph G(I) that connects identical elements. Each such graph G is a union of cliques, and we study algorithms by their worst-case running time over all inputs I' with G(I') ≅ G. We establish an adversarial lower bound showing that, for any deterministic algorithm 𝒜, there exists a graph G and an algorithm 𝒜' that, for all inputs I with G(I) ≅ G, is a factor O(log log n) faster than 𝒜. Consequently, no deterministic algorithm can be o(log log n)-competitive for all graphs G. We complement this with an O(log log n)-competitive deterministic algorithm, thereby obtaining tight bounds for element distinctness that go beyond classical worst-case analysis. Subsequently, we study the related problem of set intersection. We show that no deterministic set intersection algorithm can be o(log n)-competitive, and provide an O(log n)-competitive deterministic algorithm. We find it interesting and surprising to discover tight O(log log n)-competitive bounds for element distinctness. Moreover, we find the separation between element distinctness and the set intersection problem unexpected.},
  author       = {Van Der Hoog, Ivor and Rotenberg, Eva and Rutschmann, Daniel P},
  booktitle    = {34th Annual European Symposium on Algorithms},
  isbn         = {9783959774451},
  issn         = {1868-8969},
  keywords     = {Comparison-based analysis, set intersection, universal optimality},
  location     = {L’Aquila, Italy},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Tight Better-Than-Worst-Case bounds for element distinctness and set intersection}},
  doi          = {10.4230/LIPIcs.ESA.2026.101},
  volume       = {388},
  year         = {2026},
}