Collision finding, random walks and quantum algorithms

In this presentation, I will give a survey on the problem known as collision finding. This problem asks, given a function f:{0,1}^n->{0,1}^m to find one (or many) pairs (x,y) such that f(x)=f(y). This problem is fundamental and appears as a subroutine in many algorithms of various fields. We will see how, somewhat unexpectedly, we can use random walks on graphs to solve this problem. I will also explain how quantum algorithms can help us solve this problem faster.