Before revision: We use the recording queries technique of Zhandry [ Zha19 ] to prove lower bounds in the exponentially small success probability regime, with applications to time-space tradeoffs.
After revision: We study the problem of finding K collision pairs in a random function f : [ Zha19 ] to prove lower bounds in the exponentially small success probability regime, with applications to time-space tradeoffs.