Before revision:  Then, as an application, we prove strong direct product theorems for K-Search under a natural product distribution not considered in previous works, and for finding K distinct collisions in a uniform random function ]  . Finally, we use the latter result to obtain the first quantum time-space tradeoff that is not based on a reduction to K-Search.
After revision:  Then, as an application, we prove strong direct product theorems for K-Search under a natural product distribution not considered in previous works, and for finding K distinct collisions in a uniform random function N] . Finally, we use the latter result to obtain the first quantum time-space tradeoff that is not based on a reduction to K-Search.