  It is known that the dual of the general adversary bound can be used to build
quantum query algorithms with optimal complexity. Despite this result, not many
quantum algorithms have been designed this way. This paper shows another
example of such algorithm.
  We use the learning graph technique from arXiv:1105.4024 to give a quantum
algorithm for $k$-distinctness problem that runs in $o(n^{3/4})$ queries, for a
fixed $k$, given some prior knowledge on the structure of the input. The best
known quantum algorithm for the unconditional problem uses $O(n^{k/(k+1)})$
queries.
